/ Hex Artifact Content
Login

Artifact e93edf57832278138b98cf60cbc54241103c6988:


0000: 2f 2a 0a 2a 2a 20 32 30 30 34 20 41 70 72 69 6c  /*.** 2004 April
0010: 20 36 0a 2a 2a 0a 2a 2a 20 54 68 65 20 61 75 74   6.**.** The aut
0020: 68 6f 72 20 64 69 73 63 6c 61 69 6d 73 20 63 6f  hor disclaims co
0030: 70 79 72 69 67 68 74 20 74 6f 20 74 68 69 73 20  pyright to this 
0040: 73 6f 75 72 63 65 20 63 6f 64 65 2e 20 20 49 6e  source code.  In
0050: 20 70 6c 61 63 65 20 6f 66 0a 2a 2a 20 61 20 6c   place of.** a l
0060: 65 67 61 6c 20 6e 6f 74 69 63 65 2c 20 68 65 72  egal notice, her
0070: 65 20 69 73 20 61 20 62 6c 65 73 73 69 6e 67 3a  e is a blessing:
0080: 0a 2a 2a 0a 2a 2a 20 20 20 20 4d 61 79 20 79 6f  .**.**    May yo
0090: 75 20 64 6f 20 67 6f 6f 64 20 61 6e 64 20 6e 6f  u do good and no
00a0: 74 20 65 76 69 6c 2e 0a 2a 2a 20 20 20 20 4d 61  t evil..**    Ma
00b0: 79 20 79 6f 75 20 66 69 6e 64 20 66 6f 72 67 69  y you find forgi
00c0: 76 65 6e 65 73 73 20 66 6f 72 20 79 6f 75 72 73  veness for yours
00d0: 65 6c 66 20 61 6e 64 20 66 6f 72 67 69 76 65 20  elf and forgive 
00e0: 6f 74 68 65 72 73 2e 0a 2a 2a 20 20 20 20 4d 61  others..**    Ma
00f0: 79 20 79 6f 75 20 73 68 61 72 65 20 66 72 65 65  y you share free
0100: 6c 79 2c 20 6e 65 76 65 72 20 74 61 6b 69 6e 67  ly, never taking
0110: 20 6d 6f 72 65 20 74 68 61 6e 20 79 6f 75 20 67   more than you g
0120: 69 76 65 2e 0a 2a 2a 0a 2a 2a 2a 2a 2a 2a 2a 2a  ive..**.********
0130: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0140: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0150: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0160: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0170: 2a 0a 2a 2a 20 24 49 64 3a 20 62 74 72 65 65 49  *.** $Id: btreeI
0180: 6e 74 2e 68 2c 76 20 31 2e 38 20 32 30 30 37 2f  nt.h,v 1.8 2007/
0190: 30 38 2f 32 30 20 32 32 3a 34 38 3a 34 32 20 64  08/20 22:48:42 d
01a0: 72 68 20 45 78 70 20 24 0a 2a 2a 0a 2a 2a 20 54  rh Exp $.**.** T
01b0: 68 69 73 20 66 69 6c 65 20 69 6d 70 6c 65 6d 65  his file impleme
01c0: 6e 74 73 20 61 20 65 78 74 65 72 6e 61 6c 20 28  nts a external (
01d0: 64 69 73 6b 2d 62 61 73 65 64 29 20 64 61 74 61  disk-based) data
01e0: 62 61 73 65 20 75 73 69 6e 67 20 42 54 72 65 65  base using BTree
01f0: 73 2e 0a 2a 2a 20 46 6f 72 20 61 20 64 65 74 61  s..** For a deta
0200: 69 6c 65 64 20 64 69 73 63 75 73 73 69 6f 6e 20  iled discussion 
0210: 6f 66 20 42 54 72 65 65 73 2c 20 72 65 66 65 72  of BTrees, refer
0220: 20 74 6f 0a 2a 2a 0a 2a 2a 20 20 20 20 20 44 6f   to.**.**     Do
0230: 6e 61 6c 64 20 45 2e 20 4b 6e 75 74 68 2c 20 54  nald E. Knuth, T
0240: 48 45 20 41 52 54 20 4f 46 20 43 4f 4d 50 55 54  HE ART OF COMPUT
0250: 45 52 20 50 52 4f 47 52 41 4d 4d 49 4e 47 2c 20  ER PROGRAMMING, 
0260: 56 6f 6c 75 6d 65 20 33 3a 0a 2a 2a 20 20 20 20  Volume 3:.**    
0270: 20 22 53 6f 72 74 69 6e 67 20 41 6e 64 20 53 65   "Sorting And Se
0280: 61 72 63 68 69 6e 67 22 2c 20 70 61 67 65 73 20  arching", pages 
0290: 34 37 33 2d 34 38 30 2e 20 41 64 64 69 73 6f 6e  473-480. Addison
02a0: 2d 57 65 73 6c 65 79 0a 2a 2a 20 20 20 20 20 50  -Wesley.**     P
02b0: 75 62 6c 69 73 68 69 6e 67 20 43 6f 6d 70 61 6e  ublishing Compan
02c0: 79 2c 20 52 65 61 64 69 6e 67 2c 20 4d 61 73 73  y, Reading, Mass
02d0: 61 63 68 75 73 65 74 74 73 2e 0a 2a 2a 0a 2a 2a  achusetts..**.**
02e0: 20 54 68 65 20 62 61 73 69 63 20 69 64 65 61 20   The basic idea 
02f0: 69 73 20 74 68 61 74 20 65 61 63 68 20 70 61 67  is that each pag
0300: 65 20 6f 66 20 74 68 65 20 66 69 6c 65 20 63 6f  e of the file co
0310: 6e 74 61 69 6e 73 20 4e 20 64 61 74 61 62 61 73  ntains N databas
0320: 65 0a 2a 2a 20 65 6e 74 72 69 65 73 20 61 6e 64  e.** entries and
0330: 20 4e 2b 31 20 70 6f 69 6e 74 65 72 73 20 74 6f   N+1 pointers to
0340: 20 73 75 62 70 61 67 65 73 2e 0a 2a 2a 0a 2a 2a   subpages..**.**
0350: 20 20 20 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d     -------------
0360: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0370: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0380: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0390: 2d 2d 2d 0a 2a 2a 20 20 20 7c 20 20 50 74 72 28  ---.**   |  Ptr(
03a0: 30 29 20 7c 20 4b 65 79 28 30 29 20 7c 20 50 74  0) | Key(0) | Pt
03b0: 72 28 31 29 20 7c 20 4b 65 79 28 31 29 20 7c 20  r(1) | Key(1) | 
03c0: 2e 2e 2e 20 7c 20 4b 65 79 28 4e 2d 31 29 20 7c  ... | Key(N-1) |
03d0: 20 50 74 72 28 4e 29 20 7c 0a 2a 2a 20 20 20 2d   Ptr(N) |.**   -
03e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
03f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0400: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0410: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a  ---------------.
0420: 2a 2a 0a 2a 2a 20 41 6c 6c 20 6f 66 20 74 68 65  **.** All of the
0430: 20 6b 65 79 73 20 6f 6e 20 74 68 65 20 70 61 67   keys on the pag
0440: 65 20 74 68 61 74 20 50 74 72 28 30 29 20 70 6f  e that Ptr(0) po
0450: 69 6e 74 73 20 74 6f 20 68 61 76 65 20 76 61 6c  ints to have val
0460: 75 65 73 20 6c 65 73 73 0a 2a 2a 20 74 68 61 6e  ues less.** than
0470: 20 4b 65 79 28 30 29 2e 20 20 41 6c 6c 20 6f 66   Key(0).  All of
0480: 20 74 68 65 20 6b 65 79 73 20 6f 6e 20 70 61 67   the keys on pag
0490: 65 20 50 74 72 28 31 29 20 61 6e 64 20 69 74 73  e Ptr(1) and its
04a0: 20 73 75 62 70 61 67 65 73 20 68 61 76 65 0a 2a   subpages have.*
04b0: 2a 20 76 61 6c 75 65 73 20 67 72 65 61 74 65 72  * values greater
04c0: 20 74 68 61 6e 20 4b 65 79 28 30 29 20 61 6e 64   than Key(0) and
04d0: 20 6c 65 73 73 20 74 68 61 6e 20 4b 65 79 28 31   less than Key(1
04e0: 29 2e 20 20 41 6c 6c 20 6f 66 20 74 68 65 20 6b  ).  All of the k
04f0: 65 79 73 0a 2a 2a 20 6f 6e 20 50 74 72 28 4e 29  eys.** on Ptr(N)
0500: 20 61 6e 64 20 69 74 73 20 73 75 62 70 61 67 65   and its subpage
0510: 73 20 68 61 76 65 20 76 61 6c 75 65 73 20 67 72  s have values gr
0520: 65 61 74 65 72 20 74 68 61 6e 20 4b 65 79 28 4e  eater than Key(N
0530: 2d 31 29 2e 20 20 41 6e 64 0a 2a 2a 20 73 6f 20  -1).  And.** so 
0540: 66 6f 72 74 68 2e 0a 2a 2a 0a 2a 2a 20 46 69 6e  forth..**.** Fin
0550: 64 69 6e 67 20 61 20 70 61 72 74 69 63 75 6c 61  ding a particula
0560: 72 20 6b 65 79 20 72 65 71 75 69 72 65 73 20 72  r key requires r
0570: 65 61 64 69 6e 67 20 4f 28 6c 6f 67 28 4d 29 29  eading O(log(M))
0580: 20 70 61 67 65 73 20 66 72 6f 6d 20 74 68 65 20   pages from the 
0590: 0a 2a 2a 20 64 69 73 6b 20 77 68 65 72 65 20 4d  .** disk where M
05a0: 20 69 73 20 74 68 65 20 6e 75 6d 62 65 72 20 6f   is the number o
05b0: 66 20 65 6e 74 72 69 65 73 20 69 6e 20 74 68 65  f entries in the
05c0: 20 74 72 65 65 2e 0a 2a 2a 0a 2a 2a 20 49 6e 20   tree..**.** In 
05d0: 74 68 69 73 20 69 6d 70 6c 65 6d 65 6e 74 61 74  this implementat
05e0: 69 6f 6e 2c 20 61 20 73 69 6e 67 6c 65 20 66 69  ion, a single fi
05f0: 6c 65 20 63 61 6e 20 68 6f 6c 64 20 6f 6e 65 20  le can hold one 
0600: 6f 72 20 6d 6f 72 65 20 73 65 70 61 72 61 74 65  or more separate
0610: 20 0a 2a 2a 20 42 54 72 65 65 73 2e 20 20 45 61   .** BTrees.  Ea
0620: 63 68 20 42 54 72 65 65 20 69 73 20 69 64 65 6e  ch BTree is iden
0630: 74 69 66 69 65 64 20 62 79 20 74 68 65 20 69 6e  tified by the in
0640: 64 65 78 20 6f 66 20 69 74 73 20 72 6f 6f 74 20  dex of its root 
0650: 70 61 67 65 2e 20 20 54 68 65 0a 2a 2a 20 6b 65  page.  The.** ke
0660: 79 20 61 6e 64 20 64 61 74 61 20 66 6f 72 20 61  y and data for a
0670: 6e 79 20 65 6e 74 72 79 20 61 72 65 20 63 6f 6d  ny entry are com
0680: 62 69 6e 65 64 20 74 6f 20 66 6f 72 6d 20 74 68  bined to form th
0690: 65 20 22 70 61 79 6c 6f 61 64 22 2e 20 20 41 0a  e "payload".  A.
06a0: 2a 2a 20 66 69 78 65 64 20 61 6d 6f 75 6e 74 20  ** fixed amount 
06b0: 6f 66 20 70 61 79 6c 6f 61 64 20 63 61 6e 20 62  of payload can b
06c0: 65 20 63 61 72 72 69 65 64 20 64 69 72 65 63 74  e carried direct
06d0: 6c 79 20 6f 6e 20 74 68 65 20 64 61 74 61 62 61  ly on the databa
06e0: 73 65 0a 2a 2a 20 70 61 67 65 2e 20 20 49 66 20  se.** page.  If 
06f0: 74 68 65 20 70 61 79 6c 6f 61 64 20 69 73 20 6c  the payload is l
0700: 61 72 67 65 72 20 74 68 61 6e 20 74 68 65 20 70  arger than the p
0710: 72 65 73 65 74 20 61 6d 6f 75 6e 74 20 74 68 65  reset amount the
0720: 6e 20 73 75 72 70 6c 75 73 0a 2a 2a 20 62 79 74  n surplus.** byt
0730: 65 73 20 61 72 65 20 73 74 6f 72 65 64 20 6f 6e  es are stored on
0740: 20 6f 76 65 72 66 6c 6f 77 20 70 61 67 65 73 2e   overflow pages.
0750: 20 20 54 68 65 20 70 61 79 6c 6f 61 64 20 66 6f    The payload fo
0760: 72 20 61 6e 20 65 6e 74 72 79 0a 2a 2a 20 61 6e  r an entry.** an
0770: 64 20 74 68 65 20 70 72 65 63 65 64 69 6e 67 20  d the preceding 
0780: 70 6f 69 6e 74 65 72 20 61 72 65 20 63 6f 6d 62  pointer are comb
0790: 69 6e 65 64 20 74 6f 20 66 6f 72 6d 20 61 20 22  ined to form a "
07a0: 43 65 6c 6c 22 2e 20 20 45 61 63 68 20 0a 2a 2a  Cell".  Each .**
07b0: 20 70 61 67 65 20 68 61 73 20 61 20 73 6d 61 6c   page has a smal
07c0: 6c 20 68 65 61 64 65 72 20 77 68 69 63 68 20 63  l header which c
07d0: 6f 6e 74 61 69 6e 73 20 74 68 65 20 50 74 72 28  ontains the Ptr(
07e0: 4e 29 20 70 6f 69 6e 74 65 72 20 61 6e 64 20 6f  N) pointer and o
07f0: 74 68 65 72 0a 2a 2a 20 69 6e 66 6f 72 6d 61 74  ther.** informat
0800: 69 6f 6e 20 73 75 63 68 20 61 73 20 74 68 65 20  ion such as the 
0810: 73 69 7a 65 20 6f 66 20 6b 65 79 20 61 6e 64 20  size of key and 
0820: 64 61 74 61 2e 0a 2a 2a 0a 2a 2a 20 46 4f 52 4d  data..**.** FORM
0830: 41 54 20 44 45 54 41 49 4c 53 0a 2a 2a 0a 2a 2a  AT DETAILS.**.**
0840: 20 54 68 65 20 66 69 6c 65 20 69 73 20 64 69 76   The file is div
0850: 69 64 65 64 20 69 6e 74 6f 20 70 61 67 65 73 2e  ided into pages.
0860: 20 20 54 68 65 20 66 69 72 73 74 20 70 61 67 65    The first page
0870: 20 69 73 20 63 61 6c 6c 65 64 20 70 61 67 65 20   is called page 
0880: 31 2c 0a 2a 2a 20 74 68 65 20 73 65 63 6f 6e 64  1,.** the second
0890: 20 69 73 20 70 61 67 65 20 32 2c 20 61 6e 64 20   is page 2, and 
08a0: 73 6f 20 66 6f 72 74 68 2e 20 20 41 20 70 61 67  so forth.  A pag
08b0: 65 20 6e 75 6d 62 65 72 20 6f 66 20 7a 65 72 6f  e number of zero
08c0: 20 69 6e 64 69 63 61 74 65 73 0a 2a 2a 20 22 6e   indicates.** "n
08d0: 6f 20 73 75 63 68 20 70 61 67 65 22 2e 20 20 54  o such page".  T
08e0: 68 65 20 70 61 67 65 20 73 69 7a 65 20 63 61 6e  he page size can
08f0: 20 62 65 20 61 6e 79 74 68 69 6e 67 20 62 65 74   be anything bet
0900: 77 65 65 6e 20 35 31 32 20 61 6e 64 20 36 35 35  ween 512 and 655
0910: 33 36 2e 0a 2a 2a 20 45 61 63 68 20 70 61 67 65  36..** Each page
0920: 20 63 61 6e 20 62 65 20 65 69 74 68 65 72 20 61   can be either a
0930: 20 62 74 72 65 65 20 70 61 67 65 2c 20 61 20 66   btree page, a f
0940: 72 65 65 6c 69 73 74 20 70 61 67 65 20 6f 72 20  reelist page or 
0950: 61 6e 20 6f 76 65 72 66 6c 6f 77 0a 2a 2a 20 70  an overflow.** p
0960: 61 67 65 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 66  age..**.** The f
0970: 69 72 73 74 20 70 61 67 65 20 69 73 20 61 6c 77  irst page is alw
0980: 61 79 73 20 61 20 62 74 72 65 65 20 70 61 67 65  ays a btree page
0990: 2e 20 20 54 68 65 20 66 69 72 73 74 20 31 30 30  .  The first 100
09a0: 20 62 79 74 65 73 20 6f 66 20 74 68 65 20 66 69   bytes of the fi
09b0: 72 73 74 0a 2a 2a 20 70 61 67 65 20 63 6f 6e 74  rst.** page cont
09c0: 61 69 6e 20 61 20 73 70 65 63 69 61 6c 20 68 65  ain a special he
09d0: 61 64 65 72 20 28 74 68 65 20 22 66 69 6c 65 20  ader (the "file 
09e0: 68 65 61 64 65 72 22 29 20 74 68 61 74 20 64 65  header") that de
09f0: 73 63 72 69 62 65 73 20 74 68 65 20 66 69 6c 65  scribes the file
0a00: 2e 0a 2a 2a 20 54 68 65 20 66 6f 72 6d 61 74 20  ..** The format 
0a10: 6f 66 20 74 68 65 20 66 69 6c 65 20 68 65 61 64  of the file head
0a20: 65 72 20 69 73 20 61 73 20 66 6f 6c 6c 6f 77 73  er is as follows
0a30: 3a 0a 2a 2a 0a 2a 2a 20 20 20 4f 46 46 53 45 54  :.**.**   OFFSET
0a40: 20 20 20 53 49 5a 45 20 20 20 20 44 45 53 43 52     SIZE    DESCR
0a50: 49 50 54 49 4f 4e 0a 2a 2a 20 20 20 20 20 20 30  IPTION.**      0
0a60: 20 20 20 20 20 20 31 36 20 20 20 20 20 48 65 61        16     Hea
0a70: 64 65 72 20 73 74 72 69 6e 67 3a 20 22 53 51 4c  der string: "SQL
0a80: 69 74 65 20 66 6f 72 6d 61 74 20 33 5c 30 30 30  ite format 3\000
0a90: 22 0a 2a 2a 20 20 20 20 20 31 36 20 20 20 20 20  ".**     16     
0aa0: 20 20 32 20 20 20 20 20 50 61 67 65 20 73 69 7a    2     Page siz
0ab0: 65 20 69 6e 20 62 79 74 65 73 2e 20 20 0a 2a 2a  e in bytes.  .**
0ac0: 20 20 20 20 20 31 38 20 20 20 20 20 20 20 31 20       18       1 
0ad0: 20 20 20 20 46 69 6c 65 20 66 6f 72 6d 61 74 20      File format 
0ae0: 77 72 69 74 65 20 76 65 72 73 69 6f 6e 0a 2a 2a  write version.**
0af0: 20 20 20 20 20 31 39 20 20 20 20 20 20 20 31 20       19       1 
0b00: 20 20 20 20 46 69 6c 65 20 66 6f 72 6d 61 74 20      File format 
0b10: 72 65 61 64 20 76 65 72 73 69 6f 6e 0a 2a 2a 20  read version.** 
0b20: 20 20 20 20 32 30 20 20 20 20 20 20 20 31 20 20      20       1  
0b30: 20 20 20 42 79 74 65 73 20 6f 66 20 75 6e 75 73     Bytes of unus
0b40: 65 64 20 73 70 61 63 65 20 61 74 20 74 68 65 20  ed space at the 
0b50: 65 6e 64 20 6f 66 20 65 61 63 68 20 70 61 67 65  end of each page
0b60: 0a 2a 2a 20 20 20 20 20 32 31 20 20 20 20 20 20  .**     21      
0b70: 20 31 20 20 20 20 20 4d 61 78 20 65 6d 62 65 64   1     Max embed
0b80: 64 65 64 20 70 61 79 6c 6f 61 64 20 66 72 61 63  ded payload frac
0b90: 74 69 6f 6e 0a 2a 2a 20 20 20 20 20 32 32 20 20  tion.**     22  
0ba0: 20 20 20 20 20 31 20 20 20 20 20 4d 69 6e 20 65       1     Min e
0bb0: 6d 62 65 64 64 65 64 20 70 61 79 6c 6f 61 64 20  mbedded payload 
0bc0: 66 72 61 63 74 69 6f 6e 0a 2a 2a 20 20 20 20 20  fraction.**     
0bd0: 32 33 20 20 20 20 20 20 20 31 20 20 20 20 20 4d  23       1     M
0be0: 69 6e 20 6c 65 61 66 20 70 61 79 6c 6f 61 64 20  in leaf payload 
0bf0: 66 72 61 63 74 69 6f 6e 0a 2a 2a 20 20 20 20 20  fraction.**     
0c00: 32 34 20 20 20 20 20 20 20 34 20 20 20 20 20 46  24       4     F
0c10: 69 6c 65 20 63 68 61 6e 67 65 20 63 6f 75 6e 74  ile change count
0c20: 65 72 0a 2a 2a 20 20 20 20 20 32 38 20 20 20 20  er.**     28    
0c30: 20 20 20 34 20 20 20 20 20 52 65 73 65 72 76 65     4     Reserve
0c40: 64 20 66 6f 72 20 66 75 74 75 72 65 20 75 73 65  d for future use
0c50: 0a 2a 2a 20 20 20 20 20 33 32 20 20 20 20 20 20  .**     32      
0c60: 20 34 20 20 20 20 20 46 69 72 73 74 20 66 72 65   4     First fre
0c70: 65 6c 69 73 74 20 70 61 67 65 0a 2a 2a 20 20 20  elist page.**   
0c80: 20 20 33 36 20 20 20 20 20 20 20 34 20 20 20 20    36       4    
0c90: 20 4e 75 6d 62 65 72 20 6f 66 20 66 72 65 65 6c   Number of freel
0ca0: 69 73 74 20 70 61 67 65 73 20 69 6e 20 74 68 65  ist pages in the
0cb0: 20 66 69 6c 65 0a 2a 2a 20 20 20 20 20 34 30 20   file.**     40 
0cc0: 20 20 20 20 20 36 30 20 20 20 20 20 31 35 20 34       60     15 4
0cd0: 2d 62 79 74 65 20 6d 65 74 61 20 76 61 6c 75 65  -byte meta value
0ce0: 73 20 70 61 73 73 65 64 20 74 6f 20 68 69 67 68  s passed to high
0cf0: 65 72 20 6c 61 79 65 72 73 0a 2a 2a 0a 2a 2a 20  er layers.**.** 
0d00: 41 6c 6c 20 6f 66 20 74 68 65 20 69 6e 74 65 67  All of the integ
0d10: 65 72 20 76 61 6c 75 65 73 20 61 72 65 20 62 69  er values are bi
0d20: 67 2d 65 6e 64 69 61 6e 20 28 6d 6f 73 74 20 73  g-endian (most s
0d30: 69 67 6e 69 66 69 63 61 6e 74 20 62 79 74 65 20  ignificant byte 
0d40: 66 69 72 73 74 29 2e 0a 2a 2a 0a 2a 2a 20 54 68  first)..**.** Th
0d50: 65 20 66 69 6c 65 20 63 68 61 6e 67 65 20 63 6f  e file change co
0d60: 75 6e 74 65 72 20 69 73 20 69 6e 63 72 65 6d 65  unter is increme
0d70: 6e 74 65 64 20 77 68 65 6e 20 74 68 65 20 64 61  nted when the da
0d80: 74 61 62 61 73 65 20 69 73 20 63 68 61 6e 67 65  tabase is change
0d90: 64 0a 2a 2a 20 54 68 69 73 20 63 6f 75 6e 74 65  d.** This counte
0da0: 72 20 61 6c 6c 6f 77 73 20 6f 74 68 65 72 20 70  r allows other p
0db0: 72 6f 63 65 73 73 65 73 20 74 6f 20 6b 6e 6f 77  rocesses to know
0dc0: 20 77 68 65 6e 20 74 68 65 20 66 69 6c 65 20 68   when the file h
0dd0: 61 73 20 63 68 61 6e 67 65 64 0a 2a 2a 20 61 6e  as changed.** an
0de0: 64 20 74 68 75 73 20 77 68 65 6e 20 74 68 65 79  d thus when they
0df0: 20 6e 65 65 64 20 74 6f 20 66 6c 75 73 68 20 74   need to flush t
0e00: 68 65 69 72 20 63 61 63 68 65 2e 0a 2a 2a 0a 2a  heir cache..**.*
0e10: 2a 20 54 68 65 20 6d 61 78 20 65 6d 62 65 64 64  * The max embedd
0e20: 65 64 20 70 61 79 6c 6f 61 64 20 66 72 61 63 74  ed payload fract
0e30: 69 6f 6e 20 69 73 20 74 68 65 20 61 6d 6f 75 6e  ion is the amoun
0e40: 74 20 6f 66 20 74 68 65 20 74 6f 74 61 6c 20 75  t of the total u
0e50: 73 61 62 6c 65 0a 2a 2a 20 73 70 61 63 65 20 69  sable.** space i
0e60: 6e 20 61 20 70 61 67 65 20 74 68 61 74 20 63 61  n a page that ca
0e70: 6e 20 62 65 20 63 6f 6e 73 75 6d 65 64 20 62 79  n be consumed by
0e80: 20 61 20 73 69 6e 67 6c 65 20 63 65 6c 6c 20 66   a single cell f
0e90: 6f 72 20 73 74 61 6e 64 61 72 64 0a 2a 2a 20 42  or standard.** B
0ea0: 2d 74 72 65 65 20 28 6e 6f 6e 2d 4c 45 41 46 44  -tree (non-LEAFD
0eb0: 41 54 41 29 20 74 61 62 6c 65 73 2e 20 20 41 20  ATA) tables.  A 
0ec0: 76 61 6c 75 65 20 6f 66 20 32 35 35 20 6d 65 61  value of 255 mea
0ed0: 6e 73 20 31 30 30 25 2e 20 20 54 68 65 20 64 65  ns 100%.  The de
0ee0: 66 61 75 6c 74 0a 2a 2a 20 69 73 20 74 6f 20 6c  fault.** is to l
0ef0: 69 6d 69 74 20 74 68 65 20 6d 61 78 69 6d 75 6d  imit the maximum
0f00: 20 63 65 6c 6c 20 73 69 7a 65 20 73 6f 20 74 68   cell size so th
0f10: 61 74 20 61 74 20 6c 65 61 73 74 20 34 20 63 65  at at least 4 ce
0f20: 6c 6c 73 20 77 69 6c 6c 20 66 69 74 0a 2a 2a 20  lls will fit.** 
0f30: 6f 6e 20 6f 6e 65 20 70 61 67 65 2e 20 20 54 68  on one page.  Th
0f40: 75 73 20 74 68 65 20 64 65 66 61 75 6c 74 20 6d  us the default m
0f50: 61 78 20 65 6d 62 65 64 64 65 64 20 70 61 79 6c  ax embedded payl
0f60: 6f 61 64 20 66 72 61 63 74 69 6f 6e 20 69 73 20  oad fraction is 
0f70: 36 34 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 74 68 65  64..**.** If the
0f80: 20 70 61 79 6c 6f 61 64 20 66 6f 72 20 61 20 63   payload for a c
0f90: 65 6c 6c 20 69 73 20 6c 61 72 67 65 72 20 74 68  ell is larger th
0fa0: 61 6e 20 74 68 65 20 6d 61 78 20 70 61 79 6c 6f  an the max paylo
0fb0: 61 64 2c 20 74 68 65 6e 20 65 78 74 72 61 0a 2a  ad, then extra.*
0fc0: 2a 20 70 61 79 6c 6f 61 64 20 69 73 20 73 70 69  * payload is spi
0fd0: 6c 6c 65 64 20 74 6f 20 6f 76 65 72 66 6c 6f 77  lled to overflow
0fe0: 20 70 61 67 65 73 2e 20 20 4f 6e 63 65 20 61 6e   pages.  Once an
0ff0: 20 6f 76 65 72 66 6c 6f 77 20 70 61 67 65 20 69   overflow page i
1000: 73 20 61 6c 6c 6f 63 61 74 65 64 2c 0a 2a 2a 20  s allocated,.** 
1010: 61 73 20 6d 61 6e 79 20 62 79 74 65 73 20 61 73  as many bytes as
1020: 20 70 6f 73 73 69 62 6c 65 20 61 72 65 20 6d 6f   possible are mo
1030: 76 65 64 20 69 6e 74 6f 20 74 68 65 20 6f 76 65  ved into the ove
1040: 72 66 6c 6f 77 20 70 61 67 65 73 20 77 69 74 68  rflow pages with
1050: 6f 75 74 20 6c 65 74 74 69 6e 67 0a 2a 2a 20 74  out letting.** t
1060: 68 65 20 63 65 6c 6c 20 73 69 7a 65 20 64 72 6f  he cell size dro
1070: 70 20 62 65 6c 6f 77 20 74 68 65 20 6d 69 6e 20  p below the min 
1080: 65 6d 62 65 64 64 65 64 20 70 61 79 6c 6f 61 64  embedded payload
1090: 20 66 72 61 63 74 69 6f 6e 2e 0a 2a 2a 0a 2a 2a   fraction..**.**
10a0: 20 54 68 65 20 6d 69 6e 20 6c 65 61 66 20 70 61   The min leaf pa
10b0: 79 6c 6f 61 64 20 66 72 61 63 74 69 6f 6e 20 69  yload fraction i
10c0: 73 20 6c 69 6b 65 20 74 68 65 20 6d 69 6e 20 65  s like the min e
10d0: 6d 62 65 64 64 65 64 20 70 61 79 6c 6f 61 64 20  mbedded payload 
10e0: 66 72 61 63 74 69 6f 6e 0a 2a 2a 20 65 78 63 65  fraction.** exce
10f0: 70 74 20 74 68 61 74 20 69 74 20 61 70 70 6c 69  pt that it appli
1100: 65 73 20 74 6f 20 6c 65 61 66 20 6e 6f 64 65 73  es to leaf nodes
1110: 20 69 6e 20 61 20 4c 45 41 46 44 41 54 41 20 74   in a LEAFDATA t
1120: 72 65 65 2e 20 20 54 68 65 20 6d 61 78 69 6d 75  ree.  The maximu
1130: 6d 0a 2a 2a 20 70 61 79 6c 6f 61 64 20 66 72 61  m.** payload fra
1140: 63 74 69 6f 6e 20 66 6f 72 20 61 20 4c 45 41 46  ction for a LEAF
1150: 44 41 54 41 20 74 72 65 65 20 69 73 20 61 6c 77  DATA tree is alw
1160: 61 79 73 20 31 30 30 25 20 28 6f 72 20 32 35 35  ays 100% (or 255
1170: 29 20 61 6e 64 20 69 74 0a 2a 2a 20 6e 6f 74 20  ) and it.** not 
1180: 73 70 65 63 69 66 69 65 64 20 69 6e 20 74 68 65  specified in the
1190: 20 68 65 61 64 65 72 2e 0a 2a 2a 0a 2a 2a 20 45   header..**.** E
11a0: 61 63 68 20 62 74 72 65 65 20 70 61 67 65 73 20  ach btree pages 
11b0: 69 73 20 64 69 76 69 64 65 64 20 69 6e 74 6f 20  is divided into 
11c0: 74 68 72 65 65 20 73 65 63 74 69 6f 6e 73 3a 20  three sections: 
11d0: 20 54 68 65 20 68 65 61 64 65 72 2c 20 74 68 65   The header, the
11e0: 0a 2a 2a 20 63 65 6c 6c 20 70 6f 69 6e 74 65 72  .** cell pointer
11f0: 20 61 72 72 61 79 2c 20 61 6e 64 20 74 68 65 20   array, and the 
1200: 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 20 61 72 65  cell content are
1210: 61 2e 20 20 50 61 67 65 20 31 20 61 6c 73 6f 20  a.  Page 1 also 
1220: 68 61 73 20 61 20 31 30 30 2d 62 79 74 65 0a 2a  has a 100-byte.*
1230: 2a 20 66 69 6c 65 20 68 65 61 64 65 72 20 74 68  * file header th
1240: 61 74 20 6f 63 63 75 72 73 20 62 65 66 6f 72 65  at occurs before
1250: 20 74 68 65 20 70 61 67 65 20 68 65 61 64 65 72   the page header
1260: 2e 0a 2a 2a 0a 2a 2a 20 20 20 20 20 20 7c 2d 2d  ..**.**      |--
1270: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 7c 0a  --------------|.
1280: 2a 2a 20 20 20 20 20 20 7c 20 66 69 6c 65 20 68  **      | file h
1290: 65 61 64 65 72 20 20 20 20 7c 20 20 20 31 30 30  eader    |   100
12a0: 20 62 79 74 65 73 2e 20 20 50 61 67 65 20 31 20   bytes.  Page 1 
12b0: 6f 6e 6c 79 2e 0a 2a 2a 20 20 20 20 20 20 7c 2d  only..**      |-
12c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 7c  ---------------|
12d0: 0a 2a 2a 20 20 20 20 20 20 7c 20 70 61 67 65 20  .**      | page 
12e0: 68 65 61 64 65 72 20 20 20 20 7c 20 20 20 38 20  header    |   8 
12f0: 62 79 74 65 73 20 66 6f 72 20 6c 65 61 76 65 73  bytes for leaves
1300: 2e 20 20 31 32 20 62 79 74 65 73 20 66 6f 72 20  .  12 bytes for 
1310: 69 6e 74 65 72 69 6f 72 20 6e 6f 64 65 73 0a 2a  interior nodes.*
1320: 2a 20 20 20 20 20 20 7c 2d 2d 2d 2d 2d 2d 2d 2d  *      |--------
1330: 2d 2d 2d 2d 2d 2d 2d 2d 7c 0a 2a 2a 20 20 20 20  --------|.**    
1340: 20 20 7c 20 63 65 6c 6c 20 70 6f 69 6e 74 65 72    | cell pointer
1350: 20 20 20 7c 20 20 20 7c 20 20 32 20 62 79 74 65     |   |  2 byte
1360: 73 20 70 65 72 20 63 65 6c 6c 2e 20 20 53 6f 72  s per cell.  Sor
1370: 74 65 64 20 6f 72 64 65 72 2e 0a 2a 2a 20 20 20  ted order..**   
1380: 20 20 20 7c 20 61 72 72 61 79 20 20 20 20 20 20     | array      
1390: 20 20 20 20 7c 20 20 20 7c 20 20 47 72 6f 77 73      |   |  Grows
13a0: 20 64 6f 77 6e 77 61 72 64 0a 2a 2a 20 20 20 20   downward.**    
13b0: 20 20 7c 20 20 20 20 20 20 20 20 20 20 20 20 20    |             
13c0: 20 20 20 7c 20 20 20 76 0a 2a 2a 20 20 20 20 20     |   v.**     
13d0: 20 7c 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d   |--------------
13e0: 2d 2d 7c 0a 2a 2a 20 20 20 20 20 20 7c 20 75 6e  --|.**      | un
13f0: 61 6c 6c 6f 63 61 74 65 64 20 20 20 20 7c 0a 2a  allocated    |.*
1400: 2a 20 20 20 20 20 20 7c 20 73 70 61 63 65 20 20  *      | space  
1410: 20 20 20 20 20 20 20 20 7c 0a 2a 2a 20 20 20 20          |.**    
1420: 20 20 7c 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d    |-------------
1430: 2d 2d 2d 7c 20 20 20 5e 20 20 47 72 6f 77 73 20  ---|   ^  Grows 
1440: 75 70 77 61 72 64 73 0a 2a 2a 20 20 20 20 20 20  upwards.**      
1450: 7c 20 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 20 20  | cell content  
1460: 20 7c 20 20 20 7c 20 20 41 72 62 69 74 72 61 72   |   |  Arbitrar
1470: 79 20 6f 72 64 65 72 20 69 6e 74 65 72 73 70 65  y order interspe
1480: 72 73 65 64 20 77 69 74 68 20 66 72 65 65 62 6c  rsed with freebl
1490: 6f 63 6b 73 2e 0a 2a 2a 20 20 20 20 20 20 7c 20  ocks..**      | 
14a0: 61 72 65 61 20 20 20 20 20 20 20 20 20 20 20 7c  area           |
14b0: 20 20 20 7c 20 20 61 6e 64 20 66 72 65 65 20 73     |  and free s
14c0: 70 61 63 65 20 66 72 61 67 6d 65 6e 74 73 2e 0a  pace fragments..
14d0: 2a 2a 20 20 20 20 20 20 7c 2d 2d 2d 2d 2d 2d 2d  **      |-------
14e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 7c 0a 2a 2a 0a 2a 2a  ---------|.**.**
14f0: 20 54 68 65 20 70 61 67 65 20 68 65 61 64 65 72   The page header
1500: 73 20 6c 6f 6f 6b 73 20 6c 69 6b 65 20 74 68 69  s looks like thi
1510: 73 3a 0a 2a 2a 0a 2a 2a 20 20 20 4f 46 46 53 45  s:.**.**   OFFSE
1520: 54 20 20 20 53 49 5a 45 20 20 20 20 20 44 45 53  T   SIZE     DES
1530: 43 52 49 50 54 49 4f 4e 0a 2a 2a 20 20 20 20 20  CRIPTION.**     
1540: 20 30 20 20 20 20 20 20 20 31 20 20 20 20 20 20   0       1      
1550: 46 6c 61 67 73 2e 20 31 3a 20 69 6e 74 6b 65 79  Flags. 1: intkey
1560: 2c 20 32 3a 20 7a 65 72 6f 64 61 74 61 2c 20 34  , 2: zerodata, 4
1570: 3a 20 6c 65 61 66 64 61 74 61 2c 20 38 3a 20 6c  : leafdata, 8: l
1580: 65 61 66 0a 2a 2a 20 20 20 20 20 20 31 20 20 20  eaf.**      1   
1590: 20 20 20 20 32 20 20 20 20 20 20 62 79 74 65 20      2      byte 
15a0: 6f 66 66 73 65 74 20 74 6f 20 74 68 65 20 66 69  offset to the fi
15b0: 72 73 74 20 66 72 65 65 62 6c 6f 63 6b 0a 2a 2a  rst freeblock.**
15c0: 20 20 20 20 20 20 33 20 20 20 20 20 20 20 32 20        3       2 
15d0: 20 20 20 20 20 6e 75 6d 62 65 72 20 6f 66 20 63       number of c
15e0: 65 6c 6c 73 20 6f 6e 20 74 68 69 73 20 70 61 67  ells on this pag
15f0: 65 0a 2a 2a 20 20 20 20 20 20 35 20 20 20 20 20  e.**      5     
1600: 20 20 32 20 20 20 20 20 20 66 69 72 73 74 20 62    2      first b
1610: 79 74 65 20 6f 66 20 74 68 65 20 63 65 6c 6c 20  yte of the cell 
1620: 63 6f 6e 74 65 6e 74 20 61 72 65 61 0a 2a 2a 20  content area.** 
1630: 20 20 20 20 20 37 20 20 20 20 20 20 20 31 20 20       7       1  
1640: 20 20 20 20 6e 75 6d 62 65 72 20 6f 66 20 66 72      number of fr
1650: 61 67 6d 65 6e 74 65 64 20 66 72 65 65 20 62 79  agmented free by
1660: 74 65 73 0a 2a 2a 20 20 20 20 20 20 38 20 20 20  tes.**      8   
1670: 20 20 20 20 34 20 20 20 20 20 20 52 69 67 68 74      4      Right
1680: 20 63 68 69 6c 64 20 28 74 68 65 20 50 74 72 28   child (the Ptr(
1690: 4e 29 20 76 61 6c 75 65 29 2e 20 20 4f 6d 69 74  N) value).  Omit
16a0: 74 65 64 20 6f 6e 20 6c 65 61 76 65 73 2e 0a 2a  ted on leaves..*
16b0: 2a 0a 2a 2a 20 54 68 65 20 66 6c 61 67 73 20 64  *.** The flags d
16c0: 65 66 69 6e 65 20 74 68 65 20 66 6f 72 6d 61 74  efine the format
16d0: 20 6f 66 20 74 68 69 73 20 62 74 72 65 65 20 70   of this btree p
16e0: 61 67 65 2e 20 20 54 68 65 20 6c 65 61 66 20 66  age.  The leaf f
16f0: 6c 61 67 20 6d 65 61 6e 73 20 74 68 61 74 0a 2a  lag means that.*
1700: 2a 20 74 68 69 73 20 70 61 67 65 20 68 61 73 20  * this page has 
1710: 6e 6f 20 63 68 69 6c 64 72 65 6e 2e 20 20 54 68  no children.  Th
1720: 65 20 7a 65 72 6f 64 61 74 61 20 66 6c 61 67 20  e zerodata flag 
1730: 6d 65 61 6e 73 20 74 68 61 74 20 74 68 69 73 20  means that this 
1740: 70 61 67 65 20 63 61 72 72 69 65 73 0a 2a 2a 20  page carries.** 
1750: 6f 6e 6c 79 20 6b 65 79 73 20 61 6e 64 20 6e 6f  only keys and no
1760: 20 64 61 74 61 2e 20 20 54 68 65 20 69 6e 74 6b   data.  The intk
1770: 65 79 20 66 6c 61 67 20 6d 65 61 6e 73 20 74 68  ey flag means th
1780: 61 74 20 74 68 65 20 6b 65 79 20 69 73 20 61 20  at the key is a 
1790: 69 6e 74 65 67 65 72 0a 2a 2a 20 77 68 69 63 68  integer.** which
17a0: 20 69 73 20 73 74 6f 72 65 64 20 69 6e 20 74 68   is stored in th
17b0: 65 20 6b 65 79 20 73 69 7a 65 20 65 6e 74 72 79  e key size entry
17c0: 20 6f 66 20 74 68 65 20 63 65 6c 6c 20 68 65 61   of the cell hea
17d0: 64 65 72 20 72 61 74 68 65 72 20 74 68 61 6e 20  der rather than 
17e0: 69 6e 0a 2a 2a 20 74 68 65 20 70 61 79 6c 6f 61  in.** the payloa
17f0: 64 20 61 72 65 61 2e 0a 2a 2a 0a 2a 2a 20 54 68  d area..**.** Th
1800: 65 20 63 65 6c 6c 20 70 6f 69 6e 74 65 72 20 61  e cell pointer a
1810: 72 72 61 79 20 62 65 67 69 6e 73 20 6f 6e 20 74  rray begins on t
1820: 68 65 20 66 69 72 73 74 20 62 79 74 65 20 61 66  he first byte af
1830: 74 65 72 20 74 68 65 20 70 61 67 65 20 68 65 61  ter the page hea
1840: 64 65 72 2e 0a 2a 2a 20 54 68 65 20 63 65 6c 6c  der..** The cell
1850: 20 70 6f 69 6e 74 65 72 20 61 72 72 61 79 20 63   pointer array c
1860: 6f 6e 74 61 69 6e 73 20 7a 65 72 6f 20 6f 72 20  ontains zero or 
1870: 6d 6f 72 65 20 32 2d 62 79 74 65 20 6e 75 6d 62  more 2-byte numb
1880: 65 72 73 20 77 68 69 63 68 20 61 72 65 0a 2a 2a  ers which are.**
1890: 20 6f 66 66 73 65 74 73 20 66 72 6f 6d 20 74 68   offsets from th
18a0: 65 20 62 65 67 69 6e 6e 69 6e 67 20 6f 66 20 74  e beginning of t
18b0: 68 65 20 70 61 67 65 20 74 6f 20 74 68 65 20 63  he page to the c
18c0: 65 6c 6c 20 63 6f 6e 74 65 6e 74 20 69 6e 20 74  ell content in t
18d0: 68 65 20 63 65 6c 6c 0a 2a 2a 20 63 6f 6e 74 65  he cell.** conte
18e0: 6e 74 20 61 72 65 61 2e 20 20 54 68 65 20 63 65  nt area.  The ce
18f0: 6c 6c 20 70 6f 69 6e 74 65 72 73 20 6f 63 63 75  ll pointers occu
1900: 72 20 69 6e 20 73 6f 72 74 65 64 20 6f 72 64 65  r in sorted orde
1910: 72 2e 20 20 54 68 65 20 73 79 73 74 65 6d 20 73  r.  The system s
1920: 74 72 69 76 65 73 0a 2a 2a 20 74 6f 20 6b 65 65  trives.** to kee
1930: 70 20 66 72 65 65 20 73 70 61 63 65 20 61 66 74  p free space aft
1940: 65 72 20 74 68 65 20 6c 61 73 74 20 63 65 6c 6c  er the last cell
1950: 20 70 6f 69 6e 74 65 72 20 73 6f 20 74 68 61 74   pointer so that
1960: 20 6e 65 77 20 63 65 6c 6c 73 20 63 61 6e 0a 2a   new cells can.*
1970: 2a 20 62 65 20 65 61 73 69 6c 79 20 61 64 64 65  * be easily adde
1980: 64 20 77 69 74 68 6f 75 74 20 68 61 76 69 6e 67  d without having
1990: 20 74 6f 20 64 65 66 72 61 67 6d 65 6e 74 20 74   to defragment t
19a0: 68 65 20 70 61 67 65 2e 0a 2a 2a 0a 2a 2a 20 43  he page..**.** C
19b0: 65 6c 6c 20 63 6f 6e 74 65 6e 74 20 69 73 20 73  ell content is s
19c0: 74 6f 72 65 64 20 61 74 20 74 68 65 20 76 65 72  tored at the ver
19d0: 79 20 65 6e 64 20 6f 66 20 74 68 65 20 70 61 67  y end of the pag
19e0: 65 20 61 6e 64 20 67 72 6f 77 73 20 74 6f 77 61  e and grows towa
19f0: 72 64 20 74 68 65 0a 2a 2a 20 62 65 67 69 6e 6e  rd the.** beginn
1a00: 69 6e 67 20 6f 66 20 74 68 65 20 70 61 67 65 2e  ing of the page.
1a10: 0a 2a 2a 0a 2a 2a 20 55 6e 75 73 65 64 20 73 70  .**.** Unused sp
1a20: 61 63 65 20 77 69 74 68 69 6e 20 74 68 65 20 63  ace within the c
1a30: 65 6c 6c 20 63 6f 6e 74 65 6e 74 20 61 72 65 61  ell content area
1a40: 20 69 73 20 63 6f 6c 6c 65 63 74 65 64 20 69 6e   is collected in
1a50: 74 6f 20 61 20 6c 69 6e 6b 65 64 20 6c 69 73 74  to a linked list
1a60: 20 6f 66 0a 2a 2a 20 66 72 65 65 62 6c 6f 63 6b   of.** freeblock
1a70: 73 2e 20 20 45 61 63 68 20 66 72 65 65 62 6c 6f  s.  Each freeblo
1a80: 63 6b 20 69 73 20 61 74 20 6c 65 61 73 74 20 34  ck is at least 4
1a90: 20 62 79 74 65 73 20 69 6e 20 73 69 7a 65 2e 20   bytes in size. 
1aa0: 20 54 68 65 20 62 79 74 65 20 6f 66 66 73 65 74   The byte offset
1ab0: 0a 2a 2a 20 74 6f 20 74 68 65 20 66 69 72 73 74  .** to the first
1ac0: 20 66 72 65 65 62 6c 6f 63 6b 20 69 73 20 67 69   freeblock is gi
1ad0: 76 65 6e 20 69 6e 20 74 68 65 20 68 65 61 64 65  ven in the heade
1ae0: 72 2e 20 20 46 72 65 65 62 6c 6f 63 6b 73 20 6f  r.  Freeblocks o
1af0: 63 63 75 72 20 69 6e 0a 2a 2a 20 69 6e 63 72 65  ccur in.** incre
1b00: 61 73 69 6e 67 20 6f 72 64 65 72 2e 20 20 42 65  asing order.  Be
1b10: 63 61 75 73 65 20 61 20 66 72 65 65 62 6c 6f 63  cause a freebloc
1b20: 6b 20 6d 75 73 74 20 62 65 20 61 74 20 6c 65 61  k must be at lea
1b30: 73 74 20 34 20 62 79 74 65 73 20 69 6e 20 73 69  st 4 bytes in si
1b40: 7a 65 2c 0a 2a 2a 20 61 6e 79 20 67 72 6f 75 70  ze,.** any group
1b50: 20 6f 66 20 33 20 6f 72 20 66 65 77 65 72 20 75   of 3 or fewer u
1b60: 6e 75 73 65 64 20 62 79 74 65 73 20 69 6e 20 74  nused bytes in t
1b70: 68 65 20 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 20  he cell content 
1b80: 61 72 65 61 20 63 61 6e 6e 6f 74 0a 2a 2a 20 65  area cannot.** e
1b90: 78 69 73 74 20 6f 6e 20 74 68 65 20 66 72 65 65  xist on the free
1ba0: 62 6c 6f 63 6b 20 63 68 61 69 6e 2e 20 20 41 20  block chain.  A 
1bb0: 67 72 6f 75 70 20 6f 66 20 33 20 6f 72 20 66 65  group of 3 or fe
1bc0: 77 65 72 20 66 72 65 65 20 62 79 74 65 73 20 69  wer free bytes i
1bd0: 73 20 63 61 6c 6c 65 64 0a 2a 2a 20 61 20 66 72  s called.** a fr
1be0: 61 67 6d 65 6e 74 2e 20 20 54 68 65 20 74 6f 74  agment.  The tot
1bf0: 61 6c 20 6e 75 6d 62 65 72 20 6f 66 20 62 79 74  al number of byt
1c00: 65 73 20 69 6e 20 61 6c 6c 20 66 72 61 67 6d 65  es in all fragme
1c10: 6e 74 73 20 69 73 20 72 65 63 6f 72 64 65 64 2e  nts is recorded.
1c20: 0a 2a 2a 20 69 6e 20 74 68 65 20 70 61 67 65 20  .** in the page 
1c30: 68 65 61 64 65 72 20 61 74 20 6f 66 66 73 65 74  header at offset
1c40: 20 37 2e 0a 2a 2a 0a 2a 2a 20 20 20 20 53 49 5a   7..**.**    SIZ
1c50: 45 20 20 20 20 44 45 53 43 52 49 50 54 49 4f 4e  E    DESCRIPTION
1c60: 0a 2a 2a 20 20 20 20 20 20 32 20 20 20 20 20 42  .**      2     B
1c70: 79 74 65 20 6f 66 66 73 65 74 20 6f 66 20 74 68  yte offset of th
1c80: 65 20 6e 65 78 74 20 66 72 65 65 62 6c 6f 63 6b  e next freeblock
1c90: 0a 2a 2a 20 20 20 20 20 20 32 20 20 20 20 20 42  .**      2     B
1ca0: 79 74 65 73 20 69 6e 20 74 68 69 73 20 66 72 65  ytes in this fre
1cb0: 65 62 6c 6f 63 6b 0a 2a 2a 0a 2a 2a 20 43 65 6c  eblock.**.** Cel
1cc0: 6c 73 20 61 72 65 20 6f 66 20 76 61 72 69 61 62  ls are of variab
1cd0: 6c 65 20 6c 65 6e 67 74 68 2e 20 20 43 65 6c 6c  le length.  Cell
1ce0: 73 20 61 72 65 20 73 74 6f 72 65 64 20 69 6e 20  s are stored in 
1cf0: 74 68 65 20 63 65 6c 6c 20 63 6f 6e 74 65 6e 74  the cell content
1d00: 20 61 72 65 61 20 61 74 0a 2a 2a 20 74 68 65 20   area at.** the 
1d10: 65 6e 64 20 6f 66 20 74 68 65 20 70 61 67 65 2e  end of the page.
1d20: 20 20 50 6f 69 6e 74 65 72 73 20 74 6f 20 74 68    Pointers to th
1d30: 65 20 63 65 6c 6c 73 20 61 72 65 20 69 6e 20 74  e cells are in t
1d40: 68 65 20 63 65 6c 6c 20 70 6f 69 6e 74 65 72 20  he cell pointer 
1d50: 61 72 72 61 79 0a 2a 2a 20 74 68 61 74 20 69 6d  array.** that im
1d60: 6d 65 64 69 61 74 65 6c 79 20 66 6f 6c 6c 6f 77  mediately follow
1d70: 73 20 74 68 65 20 70 61 67 65 20 68 65 61 64 65  s the page heade
1d80: 72 2e 20 20 43 65 6c 6c 73 20 69 73 20 6e 6f 74  r.  Cells is not
1d90: 20 6e 65 63 65 73 73 61 72 69 6c 79 0a 2a 2a 20   necessarily.** 
1da0: 63 6f 6e 74 69 67 75 6f 75 73 20 6f 72 20 69 6e  contiguous or in
1db0: 20 6f 72 64 65 72 2c 20 62 75 74 20 63 65 6c 6c   order, but cell
1dc0: 20 70 6f 69 6e 74 65 72 73 20 61 72 65 20 63 6f   pointers are co
1dd0: 6e 74 69 67 75 6f 75 73 20 61 6e 64 20 69 6e 20  ntiguous and in 
1de0: 6f 72 64 65 72 2e 0a 2a 2a 0a 2a 2a 20 43 65 6c  order..**.** Cel
1df0: 6c 20 63 6f 6e 74 65 6e 74 20 6d 61 6b 65 73 20  l content makes 
1e00: 75 73 65 20 6f 66 20 76 61 72 69 61 62 6c 65 20  use of variable 
1e10: 6c 65 6e 67 74 68 20 69 6e 74 65 67 65 72 73 2e  length integers.
1e20: 20 20 41 20 76 61 72 69 61 62 6c 65 0a 2a 2a 20    A variable.** 
1e30: 6c 65 6e 67 74 68 20 69 6e 74 65 67 65 72 20 69  length integer i
1e40: 73 20 31 20 74 6f 20 39 20 62 79 74 65 73 20 77  s 1 to 9 bytes w
1e50: 68 65 72 65 20 74 68 65 20 6c 6f 77 65 72 20 37  here the lower 7
1e60: 20 62 69 74 73 20 6f 66 20 65 61 63 68 20 0a 2a   bits of each .*
1e70: 2a 20 62 79 74 65 20 61 72 65 20 75 73 65 64 2e  * byte are used.
1e80: 20 20 54 68 65 20 69 6e 74 65 67 65 72 20 63 6f    The integer co
1e90: 6e 73 69 73 74 73 20 6f 66 20 61 6c 6c 20 62 79  nsists of all by
1ea0: 74 65 73 20 74 68 61 74 20 68 61 76 65 20 62 69  tes that have bi
1eb0: 74 20 38 20 73 65 74 20 61 6e 64 0a 2a 2a 20 74  t 8 set and.** t
1ec0: 68 65 20 66 69 72 73 74 20 62 79 74 65 20 77 69  he first byte wi
1ed0: 74 68 20 62 69 74 20 38 20 63 6c 65 61 72 2e 20  th bit 8 clear. 
1ee0: 20 54 68 65 20 6d 6f 73 74 20 73 69 67 6e 69 66   The most signif
1ef0: 69 63 61 6e 74 20 62 79 74 65 20 6f 66 20 74 68  icant byte of th
1f00: 65 20 69 6e 74 65 67 65 72 0a 2a 2a 20 61 70 70  e integer.** app
1f10: 65 61 72 73 20 66 69 72 73 74 2e 20 20 41 20 76  ears first.  A v
1f20: 61 72 69 61 62 6c 65 2d 6c 65 6e 67 74 68 20 69  ariable-length i
1f30: 6e 74 65 67 65 72 20 6d 61 79 20 6e 6f 74 20 62  nteger may not b
1f40: 65 20 6d 6f 72 65 20 74 68 61 6e 20 39 20 62 79  e more than 9 by
1f50: 74 65 73 20 6c 6f 6e 67 2e 0a 2a 2a 20 41 73 20  tes long..** As 
1f60: 61 20 73 70 65 63 69 61 6c 20 63 61 73 65 2c 20  a special case, 
1f70: 61 6c 6c 20 38 20 62 79 74 65 73 20 6f 66 20 74  all 8 bytes of t
1f80: 68 65 20 39 74 68 20 62 79 74 65 20 61 72 65 20  he 9th byte are 
1f90: 75 73 65 64 20 61 73 20 64 61 74 61 2e 20 20 54  used as data.  T
1fa0: 68 69 73 0a 2a 2a 20 61 6c 6c 6f 77 73 20 61 20  his.** allows a 
1fb0: 36 34 2d 62 69 74 20 69 6e 74 65 67 65 72 20 74  64-bit integer t
1fc0: 6f 20 62 65 20 65 6e 63 6f 64 65 64 20 69 6e 20  o be encoded in 
1fd0: 39 20 62 79 74 65 73 2e 0a 2a 2a 0a 2a 2a 20 20  9 bytes..**.**  
1fe0: 20 20 30 78 30 30 20 20 20 20 20 20 20 20 20 20    0x00          
1ff0: 20 20 20 20 20 20 20 20 20 20 20 20 62 65 63 6f              beco
2000: 6d 65 73 20 20 30 78 30 30 30 30 30 30 30 30 0a  mes  0x00000000.
2010: 2a 2a 20 20 20 20 30 78 37 66 20 20 20 20 20 20  **    0x7f      
2020: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2030: 62 65 63 6f 6d 65 73 20 20 30 78 30 30 30 30 30  becomes  0x00000
2040: 30 37 66 0a 2a 2a 20 20 20 20 30 78 38 31 20 30  07f.**    0x81 0
2050: 78 30 30 20 20 20 20 20 20 20 20 20 20 20 20 20  x00             
2060: 20 20 20 20 62 65 63 6f 6d 65 73 20 20 30 78 30      becomes  0x0
2070: 30 30 30 30 30 38 30 0a 2a 2a 20 20 20 20 30 78  0000080.**    0x
2080: 38 32 20 30 78 30 30 20 20 20 20 20 20 20 20 20  82 0x00         
2090: 20 20 20 20 20 20 20 20 62 65 63 6f 6d 65 73 20          becomes 
20a0: 20 30 78 30 30 30 30 30 31 30 30 0a 2a 2a 20 20   0x00000100.**  
20b0: 20 20 30 78 38 30 20 30 78 37 66 20 20 20 20 20    0x80 0x7f     
20c0: 20 20 20 20 20 20 20 20 20 20 20 20 62 65 63 6f              beco
20d0: 6d 65 73 20 20 30 78 30 30 30 30 30 30 37 66 0a  mes  0x0000007f.
20e0: 2a 2a 20 20 20 20 30 78 38 61 20 30 78 39 31 20  **    0x8a 0x91 
20f0: 30 78 64 31 20 30 78 61 63 20 30 78 37 38 20 20  0xd1 0xac 0x78  
2100: 62 65 63 6f 6d 65 73 20 20 30 78 31 32 33 34 35  becomes  0x12345
2110: 36 37 38 0a 2a 2a 20 20 20 20 30 78 38 31 20 30  678.**    0x81 0
2120: 78 38 31 20 30 78 38 31 20 30 78 38 31 20 30 78  x81 0x81 0x81 0x
2130: 30 31 20 20 62 65 63 6f 6d 65 73 20 20 30 78 31  01  becomes  0x1
2140: 30 32 30 34 30 38 31 0a 2a 2a 0a 2a 2a 20 56 61  0204081.**.** Va
2150: 72 69 61 62 6c 65 20 6c 65 6e 67 74 68 20 69 6e  riable length in
2160: 74 65 67 65 72 73 20 61 72 65 20 75 73 65 64 20  tegers are used 
2170: 66 6f 72 20 72 6f 77 69 64 73 20 61 6e 64 20 74  for rowids and t
2180: 6f 20 68 6f 6c 64 20 74 68 65 20 6e 75 6d 62 65  o hold the numbe
2190: 72 20 6f 66 0a 2a 2a 20 62 79 74 65 73 20 6f 66  r of.** bytes of
21a0: 20 6b 65 79 20 61 6e 64 20 64 61 74 61 20 69 6e   key and data in
21b0: 20 61 20 62 74 72 65 65 20 63 65 6c 6c 2e 0a 2a   a btree cell..*
21c0: 2a 0a 2a 2a 20 54 68 65 20 63 6f 6e 74 65 6e 74  *.** The content
21d0: 20 6f 66 20 61 20 63 65 6c 6c 20 6c 6f 6f 6b 73   of a cell looks
21e0: 20 6c 69 6b 65 20 74 68 69 73 3a 0a 2a 2a 0a 2a   like this:.**.*
21f0: 2a 20 20 20 20 53 49 5a 45 20 20 20 20 44 45 53  *    SIZE    DES
2200: 43 52 49 50 54 49 4f 4e 0a 2a 2a 20 20 20 20 20  CRIPTION.**     
2210: 20 34 20 20 20 20 20 50 61 67 65 20 6e 75 6d 62   4     Page numb
2220: 65 72 20 6f 66 20 74 68 65 20 6c 65 66 74 20 63  er of the left c
2230: 68 69 6c 64 2e 20 4f 6d 69 74 74 65 64 20 69 66  hild. Omitted if
2240: 20 6c 65 61 66 20 66 6c 61 67 20 69 73 20 73 65   leaf flag is se
2250: 74 2e 0a 2a 2a 20 20 20 20 20 76 61 72 20 20 20  t..**     var   
2260: 20 4e 75 6d 62 65 72 20 6f 66 20 62 79 74 65 73   Number of bytes
2270: 20 6f 66 20 64 61 74 61 2e 20 4f 6d 69 74 74 65   of data. Omitte
2280: 64 20 69 66 20 74 68 65 20 7a 65 72 6f 64 61 74  d if the zerodat
2290: 61 20 66 6c 61 67 20 69 73 20 73 65 74 2e 0a 2a  a flag is set..*
22a0: 2a 20 20 20 20 20 76 61 72 20 20 20 20 4e 75 6d  *     var    Num
22b0: 62 65 72 20 6f 66 20 62 79 74 65 73 20 6f 66 20  ber of bytes of 
22c0: 6b 65 79 2e 20 4f 72 20 74 68 65 20 6b 65 79 20  key. Or the key 
22d0: 69 74 73 65 6c 66 20 69 66 20 69 6e 74 6b 65 79  itself if intkey
22e0: 20 66 6c 61 67 20 69 73 20 73 65 74 2e 0a 2a 2a   flag is set..**
22f0: 20 20 20 20 20 20 2a 20 20 20 20 20 50 61 79 6c        *     Payl
2300: 6f 61 64 0a 2a 2a 20 20 20 20 20 20 34 20 20 20  oad.**      4   
2310: 20 20 46 69 72 73 74 20 70 61 67 65 20 6f 66 20    First page of 
2320: 74 68 65 20 6f 76 65 72 66 6c 6f 77 20 63 68 61  the overflow cha
2330: 69 6e 2e 20 20 4f 6d 69 74 74 65 64 20 69 66 20  in.  Omitted if 
2340: 6e 6f 20 6f 76 65 72 66 6c 6f 77 0a 2a 2a 0a 2a  no overflow.**.*
2350: 2a 20 4f 76 65 72 66 6c 6f 77 20 70 61 67 65 73  * Overflow pages
2360: 20 66 6f 72 6d 20 61 20 6c 69 6e 6b 65 64 20 6c   form a linked l
2370: 69 73 74 2e 20 20 45 61 63 68 20 70 61 67 65 20  ist.  Each page 
2380: 65 78 63 65 70 74 20 74 68 65 20 6c 61 73 74 20  except the last 
2390: 69 73 20 63 6f 6d 70 6c 65 74 65 6c 79 0a 2a 2a  is completely.**
23a0: 20 66 69 6c 6c 65 64 20 77 69 74 68 20 64 61 74   filled with dat
23b0: 61 20 28 70 61 67 65 73 69 7a 65 20 2d 20 34 20  a (pagesize - 4 
23c0: 62 79 74 65 73 29 2e 20 20 54 68 65 20 6c 61 73  bytes).  The las
23d0: 74 20 70 61 67 65 20 63 61 6e 20 68 61 76 65 20  t page can have 
23e0: 61 73 20 6c 69 74 74 6c 65 0a 2a 2a 20 61 73 20  as little.** as 
23f0: 31 20 62 79 74 65 20 6f 66 20 64 61 74 61 2e 0a  1 byte of data..
2400: 2a 2a 0a 2a 2a 20 20 20 20 53 49 5a 45 20 20 20  **.**    SIZE   
2410: 20 44 45 53 43 52 49 50 54 49 4f 4e 0a 2a 2a 20   DESCRIPTION.** 
2420: 20 20 20 20 20 34 20 20 20 20 20 50 61 67 65 20       4     Page 
2430: 6e 75 6d 62 65 72 20 6f 66 20 6e 65 78 74 20 6f  number of next o
2440: 76 65 72 66 6c 6f 77 20 70 61 67 65 0a 2a 2a 20  verflow page.** 
2450: 20 20 20 20 20 2a 20 20 20 20 20 44 61 74 61 0a       *     Data.
2460: 2a 2a 0a 2a 2a 20 46 72 65 65 6c 69 73 74 20 70  **.** Freelist p
2470: 61 67 65 73 20 63 6f 6d 65 20 69 6e 20 74 77 6f  ages come in two
2480: 20 73 75 62 74 79 70 65 73 3a 20 74 72 75 6e 6b   subtypes: trunk
2490: 20 70 61 67 65 73 20 61 6e 64 20 6c 65 61 66 20   pages and leaf 
24a0: 70 61 67 65 73 2e 20 20 54 68 65 0a 2a 2a 20 66  pages.  The.** f
24b0: 69 6c 65 20 68 65 61 64 65 72 20 70 6f 69 6e 74  ile header point
24c0: 73 20 74 6f 20 74 68 65 20 66 69 72 73 74 20 69  s to the first i
24d0: 6e 20 61 20 6c 69 6e 6b 65 64 20 6c 69 73 74 20  n a linked list 
24e0: 6f 66 20 74 72 75 6e 6b 20 70 61 67 65 2e 20 20  of trunk page.  
24f0: 45 61 63 68 20 74 72 75 6e 6b 0a 2a 2a 20 70 61  Each trunk.** pa
2500: 67 65 20 70 6f 69 6e 74 73 20 74 6f 20 6d 75 6c  ge points to mul
2510: 74 69 70 6c 65 20 6c 65 61 66 20 70 61 67 65 73  tiple leaf pages
2520: 2e 20 20 54 68 65 20 63 6f 6e 74 65 6e 74 20 6f  .  The content o
2530: 66 20 61 20 6c 65 61 66 20 70 61 67 65 20 69 73  f a leaf page is
2540: 0a 2a 2a 20 75 6e 73 70 65 63 69 66 69 65 64 2e  .** unspecified.
2550: 20 20 41 20 74 72 75 6e 6b 20 70 61 67 65 20 6c    A trunk page l
2560: 6f 6f 6b 73 20 6c 69 6b 65 20 74 68 69 73 3a 0a  ooks like this:.
2570: 2a 2a 0a 2a 2a 20 20 20 20 53 49 5a 45 20 20 20  **.**    SIZE   
2580: 20 44 45 53 43 52 49 50 54 49 4f 4e 0a 2a 2a 20   DESCRIPTION.** 
2590: 20 20 20 20 20 34 20 20 20 20 20 50 61 67 65 20       4     Page 
25a0: 6e 75 6d 62 65 72 20 6f 66 20 6e 65 78 74 20 74  number of next t
25b0: 72 75 6e 6b 20 70 61 67 65 0a 2a 2a 20 20 20 20  runk page.**    
25c0: 20 20 34 20 20 20 20 20 4e 75 6d 62 65 72 20 6f    4     Number o
25d0: 66 20 6c 65 61 66 20 70 6f 69 6e 74 65 72 73 20  f leaf pointers 
25e0: 6f 6e 20 74 68 69 73 20 70 61 67 65 0a 2a 2a 20  on this page.** 
25f0: 20 20 20 20 20 2a 20 20 20 20 20 7a 65 72 6f 20       *     zero 
2600: 6f 72 20 6d 6f 72 65 20 70 61 67 65 73 20 6e 75  or more pages nu
2610: 6d 62 65 72 73 20 6f 66 20 6c 65 61 76 65 73 0a  mbers of leaves.
2620: 2a 2f 0a 23 69 6e 63 6c 75 64 65 20 22 73 71 6c  */.#include "sql
2630: 69 74 65 49 6e 74 2e 68 22 0a 23 69 6e 63 6c 75  iteInt.h".#inclu
2640: 64 65 20 22 70 61 67 65 72 2e 68 22 0a 23 69 6e  de "pager.h".#in
2650: 63 6c 75 64 65 20 22 62 74 72 65 65 2e 68 22 0a  clude "btree.h".
2660: 23 69 6e 63 6c 75 64 65 20 22 6f 73 2e 68 22 0a  #include "os.h".
2670: 23 69 6e 63 6c 75 64 65 20 3c 61 73 73 65 72 74  #include <assert
2680: 2e 68 3e 0a 0a 2f 2a 20 52 6f 75 6e 64 20 75 70  .h>../* Round up
2690: 20 61 20 6e 75 6d 62 65 72 20 74 6f 20 74 68 65   a number to the
26a0: 20 6e 65 78 74 20 6c 61 72 67 65 72 20 6d 75 6c   next larger mul
26b0: 74 69 70 6c 65 20 6f 66 20 38 2e 20 20 54 68 69  tiple of 8.  Thi
26c0: 73 20 69 73 20 75 73 65 64 0a 2a 2a 20 74 6f 20  s is used.** to 
26d0: 66 6f 72 63 65 20 38 2d 62 79 74 65 20 61 6c 69  force 8-byte ali
26e0: 67 6e 6d 65 6e 74 20 6f 6e 20 36 34 2d 62 69 74  gnment on 64-bit
26f0: 20 61 72 63 68 69 74 65 63 74 75 72 65 73 2e 0a   architectures..
2700: 2a 2f 0a 23 64 65 66 69 6e 65 20 52 4f 55 4e 44  */.#define ROUND
2710: 38 28 78 29 20 20 20 28 28 78 2b 37 29 26 7e 37  8(x)   ((x+7)&~7
2720: 29 0a 0a 0a 2f 2a 20 54 68 65 20 66 6f 6c 6c 6f  ).../* The follo
2730: 77 69 6e 67 20 76 61 6c 75 65 20 69 73 20 74 68  wing value is th
2740: 65 20 6d 61 78 69 6d 75 6d 20 63 65 6c 6c 20 73  e maximum cell s
2750: 69 7a 65 20 61 73 73 75 6d 69 6e 67 20 61 20 6d  ize assuming a m
2760: 61 78 69 6d 75 6d 20 70 61 67 65 0a 2a 2a 20 73  aximum page.** s
2770: 69 7a 65 20 67 69 76 65 20 61 62 6f 76 65 2e 0a  ize give above..
2780: 2a 2f 0a 23 64 65 66 69 6e 65 20 4d 58 5f 43 45  */.#define MX_CE
2790: 4c 4c 5f 53 49 5a 45 28 70 42 74 29 20 20 28 70  LL_SIZE(pBt)  (p
27a0: 42 74 2d 3e 70 61 67 65 53 69 7a 65 2d 38 29 0a  Bt->pageSize-8).
27b0: 0a 2f 2a 20 54 68 65 20 6d 61 78 69 6d 75 6d 20  ./* The maximum 
27c0: 6e 75 6d 62 65 72 20 6f 66 20 63 65 6c 6c 73 20  number of cells 
27d0: 6f 6e 20 61 20 73 69 6e 67 6c 65 20 70 61 67 65  on a single page
27e0: 20 6f 66 20 74 68 65 20 64 61 74 61 62 61 73 65   of the database
27f0: 2e 20 20 54 68 69 73 0a 2a 2a 20 61 73 73 75 6d  .  This.** assum
2800: 65 73 20 61 20 6d 69 6e 69 6d 75 6d 20 63 65 6c  es a minimum cel
2810: 6c 20 73 69 7a 65 20 6f 66 20 33 20 62 79 74 65  l size of 3 byte
2820: 73 2e 20 20 53 75 63 68 20 73 6d 61 6c 6c 20 63  s.  Such small c
2830: 65 6c 6c 73 20 77 69 6c 6c 20 62 65 0a 2a 2a 20  ells will be.** 
2840: 65 78 63 65 65 64 69 6e 67 6c 79 20 72 61 72 65  exceedingly rare
2850: 2c 20 62 75 74 20 74 68 65 79 20 61 72 65 20 70  , but they are p
2860: 6f 73 73 69 62 6c 65 2e 0a 2a 2f 0a 23 64 65 66  ossible..*/.#def
2870: 69 6e 65 20 4d 58 5f 43 45 4c 4c 28 70 42 74 29  ine MX_CELL(pBt)
2880: 20 28 28 70 42 74 2d 3e 70 61 67 65 53 69 7a 65   ((pBt->pageSize
2890: 2d 38 29 2f 33 29 0a 0a 2f 2a 20 46 6f 72 77 61  -8)/3)../* Forwa
28a0: 72 64 20 64 65 63 6c 61 72 61 74 69 6f 6e 73 20  rd declarations 
28b0: 2a 2f 0a 74 79 70 65 64 65 66 20 73 74 72 75 63  */.typedef struc
28c0: 74 20 4d 65 6d 50 61 67 65 20 4d 65 6d 50 61 67  t MemPage MemPag
28d0: 65 3b 0a 74 79 70 65 64 65 66 20 73 74 72 75 63  e;.typedef struc
28e0: 74 20 42 74 4c 6f 63 6b 20 42 74 4c 6f 63 6b 3b  t BtLock BtLock;
28f0: 0a 0a 2f 2a 0a 2a 2a 20 54 68 69 73 20 69 73 20  ../*.** This is 
2900: 61 20 6d 61 67 69 63 20 73 74 72 69 6e 67 20 74  a magic string t
2910: 68 61 74 20 61 70 70 65 61 72 73 20 61 74 20 74  hat appears at t
2920: 68 65 20 62 65 67 69 6e 6e 69 6e 67 20 6f 66 20  he beginning of 
2930: 65 76 65 72 79 0a 2a 2a 20 53 51 4c 69 74 65 20  every.** SQLite 
2940: 64 61 74 61 62 61 73 65 20 69 6e 20 6f 72 64 65  database in orde
2950: 72 20 74 6f 20 69 64 65 6e 74 69 66 79 20 74 68  r to identify th
2960: 65 20 66 69 6c 65 20 61 73 20 61 20 72 65 61 6c  e file as a real
2970: 20 64 61 74 61 62 61 73 65 2e 0a 2a 2a 0a 2a 2a   database..**.**
2980: 20 59 6f 75 20 63 61 6e 20 63 68 61 6e 67 65 20   You can change 
2990: 74 68 69 73 20 76 61 6c 75 65 20 61 74 20 63 6f  this value at co
29a0: 6d 70 69 6c 65 2d 74 69 6d 65 20 62 79 20 73 70  mpile-time by sp
29b0: 65 63 69 66 79 69 6e 67 20 61 0a 2a 2a 20 2d 44  ecifying a.** -D
29c0: 53 51 4c 49 54 45 5f 46 49 4c 45 5f 48 45 41 44  SQLITE_FILE_HEAD
29d0: 45 52 3d 22 2e 2e 2e 22 20 6f 6e 20 74 68 65 20  ER="..." on the 
29e0: 63 6f 6d 70 69 6c 65 72 20 63 6f 6d 6d 61 6e 64  compiler command
29f0: 2d 6c 69 6e 65 2e 20 20 54 68 65 0a 2a 2a 20 68  -line.  The.** h
2a00: 65 61 64 65 72 20 6d 75 73 74 20 62 65 20 65 78  eader must be ex
2a10: 61 63 74 6c 79 20 31 36 20 62 79 74 65 73 20 69  actly 16 bytes i
2a20: 6e 63 6c 75 64 69 6e 67 20 74 68 65 20 7a 65 72  ncluding the zer
2a30: 6f 2d 74 65 72 6d 69 6e 61 74 6f 72 20 73 6f 0a  o-terminator so.
2a40: 2a 2a 20 74 68 65 20 73 74 72 69 6e 67 20 69 74  ** the string it
2a50: 73 65 6c 66 20 73 68 6f 75 6c 64 20 62 65 20 31  self should be 1
2a60: 35 20 63 68 61 72 61 63 74 65 72 73 20 6c 6f 6e  5 characters lon
2a70: 67 2e 20 20 49 66 20 79 6f 75 20 63 68 61 6e 67  g.  If you chang
2a80: 65 0a 2a 2a 20 74 68 65 20 68 65 61 64 65 72 2c  e.** the header,
2a90: 20 74 68 65 6e 20 79 6f 75 72 20 63 75 73 74 6f   then your custo
2aa0: 6d 20 6c 69 62 72 61 72 79 20 77 69 6c 6c 20 6e  m library will n
2ab0: 6f 74 20 62 65 20 61 62 6c 65 20 74 6f 20 72 65  ot be able to re
2ac0: 61 64 20 0a 2a 2a 20 64 61 74 61 62 61 73 65 73  ad .** databases
2ad0: 20 67 65 6e 65 72 61 74 65 64 20 62 79 20 74 68   generated by th
2ae0: 65 20 73 74 61 6e 64 61 72 64 20 74 6f 6f 6c 73  e standard tools
2af0: 20 61 6e 64 20 74 68 65 20 73 74 61 6e 64 61 72   and the standar
2b00: 64 20 74 6f 6f 6c 73 0a 2a 2a 20 77 69 6c 6c 20  d tools.** will 
2b10: 6e 6f 74 20 62 65 20 61 62 6c 65 20 74 6f 20 72  not be able to r
2b20: 65 61 64 20 64 61 74 61 62 61 73 65 73 20 63 72  ead databases cr
2b30: 65 61 74 65 64 20 62 79 20 79 6f 75 72 20 63 75  eated by your cu
2b40: 73 74 6f 6d 20 6c 69 62 72 61 72 79 2e 0a 2a 2f  stom library..*/
2b50: 0a 23 69 66 6e 64 65 66 20 53 51 4c 49 54 45 5f  .#ifndef SQLITE_
2b60: 46 49 4c 45 5f 48 45 41 44 45 52 20 2f 2a 20 31  FILE_HEADER /* 1
2b70: 32 33 34 35 36 37 38 39 20 31 32 33 34 35 36 20  23456789 123456 
2b80: 2a 2f 0a 23 20 20 64 65 66 69 6e 65 20 53 51 4c  */.#  define SQL
2b90: 49 54 45 5f 46 49 4c 45 5f 48 45 41 44 45 52 20  ITE_FILE_HEADER 
2ba0: 22 53 51 4c 69 74 65 20 66 6f 72 6d 61 74 20 33  "SQLite format 3
2bb0: 22 0a 23 65 6e 64 69 66 0a 0a 2f 2a 0a 2a 2a 20  ".#endif../*.** 
2bc0: 50 61 67 65 20 74 79 70 65 20 66 6c 61 67 73 2e  Page type flags.
2bd0: 20 20 41 6e 20 4f 52 65 64 20 63 6f 6d 62 69 6e    An ORed combin
2be0: 61 74 69 6f 6e 20 6f 66 20 74 68 65 73 65 20 66  ation of these f
2bf0: 6c 61 67 73 20 61 70 70 65 61 72 20 61 73 20 74  lags appear as t
2c00: 68 65 0a 2a 2a 20 66 69 72 73 74 20 62 79 74 65  he.** first byte
2c10: 20 6f 66 20 6f 6e 2d 64 69 73 6b 20 69 6d 61 67   of on-disk imag
2c20: 65 20 6f 66 20 65 76 65 72 79 20 42 54 72 65 65  e of every BTree
2c30: 20 70 61 67 65 2e 0a 2a 2f 0a 23 64 65 66 69 6e   page..*/.#defin
2c40: 65 20 50 54 46 5f 49 4e 54 4b 45 59 20 20 20 20  e PTF_INTKEY    
2c50: 30 78 30 31 0a 23 64 65 66 69 6e 65 20 50 54 46  0x01.#define PTF
2c60: 5f 5a 45 52 4f 44 41 54 41 20 20 30 78 30 32 0a  _ZERODATA  0x02.
2c70: 23 64 65 66 69 6e 65 20 50 54 46 5f 4c 45 41 46  #define PTF_LEAF
2c80: 44 41 54 41 20 20 30 78 30 34 0a 23 64 65 66 69  DATA  0x04.#defi
2c90: 6e 65 20 50 54 46 5f 4c 45 41 46 20 20 20 20 20  ne PTF_LEAF     
2ca0: 20 30 78 30 38 0a 0a 2f 2a 0a 2a 2a 20 41 73 20   0x08../*.** As 
2cb0: 65 61 63 68 20 70 61 67 65 20 6f 66 20 74 68 65  each page of the
2cc0: 20 66 69 6c 65 20 69 73 20 6c 6f 61 64 65 64 20   file is loaded 
2cd0: 69 6e 74 6f 20 6d 65 6d 6f 72 79 2c 20 61 6e 20  into memory, an 
2ce0: 69 6e 73 74 61 6e 63 65 20 6f 66 20 74 68 65 20  instance of the 
2cf0: 66 6f 6c 6c 6f 77 69 6e 67 0a 2a 2a 20 73 74 72  following.** str
2d00: 75 63 74 75 72 65 20 69 73 20 61 70 70 65 6e 64  ucture is append
2d10: 65 64 20 61 6e 64 20 69 6e 69 74 69 61 6c 69 7a  ed and initializ
2d20: 65 64 20 74 6f 20 7a 65 72 6f 2e 20 20 54 68 69  ed to zero.  Thi
2d30: 73 20 73 74 72 75 63 74 75 72 65 20 73 74 6f 72  s structure stor
2d40: 65 73 0a 2a 2a 20 69 6e 66 6f 72 6d 61 74 69 6f  es.** informatio
2d50: 6e 20 61 62 6f 75 74 20 74 68 65 20 70 61 67 65  n about the page
2d60: 20 74 68 61 74 20 69 73 20 64 65 63 6f 64 65 64   that is decoded
2d70: 20 66 72 6f 6d 20 74 68 65 20 72 61 77 20 66 69   from the raw fi
2d80: 6c 65 20 70 61 67 65 2e 0a 2a 2a 0a 2a 2a 20 54  le page..**.** T
2d90: 68 65 20 70 50 61 72 65 6e 74 20 66 69 65 6c 64  he pParent field
2da0: 20 70 6f 69 6e 74 73 20 62 61 63 6b 20 74 6f 20   points back to 
2db0: 74 68 65 20 70 61 72 65 6e 74 20 70 61 67 65 2e  the parent page.
2dc0: 20 20 54 68 69 73 20 61 6c 6c 6f 77 73 20 75 73    This allows us
2dd0: 20 74 6f 0a 2a 2a 20 77 61 6c 6b 20 75 70 20 74   to.** walk up t
2de0: 68 65 20 42 54 72 65 65 20 66 72 6f 6d 20 61 6e  he BTree from an
2df0: 79 20 6c 65 61 66 20 74 6f 20 74 68 65 20 72 6f  y leaf to the ro
2e00: 6f 74 2e 20 20 43 61 72 65 20 6d 75 73 74 20 62  ot.  Care must b
2e10: 65 20 74 61 6b 65 6e 20 74 6f 0a 2a 2a 20 75 6e  e taken to.** un
2e20: 72 65 66 28 29 20 74 68 65 20 70 61 72 65 6e 74  ref() the parent
2e30: 20 70 61 67 65 20 70 6f 69 6e 74 65 72 20 77 68   page pointer wh
2e40: 65 6e 20 74 68 69 73 20 70 61 67 65 20 69 73 20  en this page is 
2e50: 6e 6f 20 6c 6f 6e 67 65 72 20 72 65 66 65 72 65  no longer refere
2e60: 6e 63 65 64 2e 0a 2a 2a 20 54 68 65 20 70 61 67  nced..** The pag
2e70: 65 44 65 73 74 72 75 63 74 6f 72 28 29 20 72 6f  eDestructor() ro
2e80: 75 74 69 6e 65 20 68 61 6e 64 6c 65 73 20 74 68  utine handles th
2e90: 61 74 20 63 68 6f 72 65 2e 0a 2a 2a 0a 2a 2a 20  at chore..**.** 
2ea0: 41 63 63 65 73 73 20 74 6f 20 61 6c 6c 20 66 69  Access to all fi
2eb0: 65 6c 64 73 20 6f 66 20 74 68 69 73 20 73 74 72  elds of this str
2ec0: 75 63 74 75 72 65 20 69 73 20 63 6f 6e 74 72 6f  ucture is contro
2ed0: 6c 6c 65 64 20 62 79 20 74 68 65 20 6d 75 74 65  lled by the mute
2ee0: 78 0a 2a 2a 20 73 74 6f 72 65 64 20 69 6e 20 4d  x.** stored in M
2ef0: 65 6d 50 61 67 65 2e 70 42 74 2d 3e 6d 75 74 65  emPage.pBt->mute
2f00: 78 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 4d 65 6d  x..*/.struct Mem
2f10: 50 61 67 65 20 7b 0a 20 20 75 38 20 69 73 49 6e  Page {.  u8 isIn
2f20: 69 74 3b 20 20 20 20 20 20 20 20 20 20 20 2f 2a  it;           /*
2f30: 20 54 72 75 65 20 69 66 20 70 72 65 76 69 6f 75   True if previou
2f40: 73 6c 79 20 69 6e 69 74 69 61 6c 69 7a 65 64 2e  sly initialized.
2f50: 20 4d 55 53 54 20 42 45 20 46 49 52 53 54 21 20   MUST BE FIRST! 
2f60: 2a 2f 0a 20 20 75 38 20 69 64 78 53 68 69 66 74  */.  u8 idxShift
2f70: 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75  ;         /* Tru
2f80: 65 20 69 66 20 43 65 6c 6c 20 69 6e 64 69 63 65  e if Cell indice
2f90: 73 20 68 61 76 65 20 63 68 61 6e 67 65 64 20 2a  s have changed *
2fa0: 2f 0a 20 20 75 38 20 6e 4f 76 65 72 66 6c 6f 77  /.  u8 nOverflow
2fb0: 3b 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62  ;        /* Numb
2fc0: 65 72 20 6f 66 20 6f 76 65 72 66 6c 6f 77 20 63  er of overflow c
2fd0: 65 6c 6c 20 62 6f 64 69 65 73 20 69 6e 20 61 43  ell bodies in aC
2fe0: 65 6c 6c 5b 5d 20 2a 2f 0a 20 20 75 38 20 69 6e  ell[] */.  u8 in
2ff0: 74 4b 65 79 3b 20 20 20 20 20 20 20 20 20 20 20  tKey;           
3000: 2f 2a 20 54 72 75 65 20 69 66 20 69 6e 74 6b 65  /* True if intke
3010: 79 20 66 6c 61 67 20 69 73 20 73 65 74 20 2a 2f  y flag is set */
3020: 0a 20 20 75 38 20 6c 65 61 66 3b 20 20 20 20 20  .  u8 leaf;     
3030: 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20          /* True 
3040: 69 66 20 6c 65 61 66 20 66 6c 61 67 20 69 73 20  if leaf flag is 
3050: 73 65 74 20 2a 2f 0a 20 20 75 38 20 7a 65 72 6f  set */.  u8 zero
3060: 44 61 74 61 3b 20 20 20 20 20 20 20 20 20 2f 2a  Data;         /*
3070: 20 54 72 75 65 20 69 66 20 74 61 62 6c 65 20 73   True if table s
3080: 74 6f 72 65 73 20 6b 65 79 73 20 6f 6e 6c 79 20  tores keys only 
3090: 2a 2f 0a 20 20 75 38 20 6c 65 61 66 44 61 74 61  */.  u8 leafData
30a0: 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75  ;         /* Tru
30b0: 65 20 69 66 20 74 61 62 6c 65 73 20 73 74 6f 72  e if tables stor
30c0: 65 73 20 64 61 74 61 20 6f 6e 20 6c 65 61 76 65  es data on leave
30d0: 73 20 6f 6e 6c 79 20 2a 2f 0a 20 20 75 38 20 68  s only */.  u8 h
30e0: 61 73 44 61 74 61 3b 20 20 20 20 20 20 20 20 20  asData;         
30f0: 20 2f 2a 20 54 72 75 65 20 69 66 20 74 68 69 73   /* True if this
3100: 20 70 61 67 65 20 73 74 6f 72 65 73 20 64 61 74   page stores dat
3110: 61 20 2a 2f 0a 20 20 75 38 20 68 64 72 4f 66 66  a */.  u8 hdrOff
3120: 73 65 74 3b 20 20 20 20 20 20 20 20 2f 2a 20 31  set;        /* 1
3130: 30 30 20 66 6f 72 20 70 61 67 65 20 31 2e 20 20  00 for page 1.  
3140: 30 20 6f 74 68 65 72 77 69 73 65 20 2a 2f 0a 20  0 otherwise */. 
3150: 20 75 38 20 63 68 69 6c 64 50 74 72 53 69 7a 65   u8 childPtrSize
3160: 3b 20 20 20 20 20 2f 2a 20 30 20 69 66 20 6c 65  ;     /* 0 if le
3170: 61 66 3d 3d 31 2e 20 20 34 20 69 66 20 6c 65 61  af==1.  4 if lea
3180: 66 3d 3d 30 20 2a 2f 0a 20 20 75 31 36 20 6d 61  f==0 */.  u16 ma
3190: 78 4c 6f 63 61 6c 3b 20 20 20 20 20 20 20 20 2f  xLocal;        /
31a0: 2a 20 43 6f 70 79 20 6f 66 20 42 74 53 68 61 72  * Copy of BtShar
31b0: 65 64 2e 6d 61 78 4c 6f 63 61 6c 20 6f 72 20 42  ed.maxLocal or B
31c0: 74 53 68 61 72 65 64 2e 6d 61 78 4c 65 61 66 20  tShared.maxLeaf 
31d0: 2a 2f 0a 20 20 75 31 36 20 6d 69 6e 4c 6f 63 61  */.  u16 minLoca
31e0: 6c 3b 20 20 20 20 20 20 20 20 2f 2a 20 43 6f 70  l;        /* Cop
31f0: 79 20 6f 66 20 42 74 53 68 61 72 65 64 2e 6d 69  y of BtShared.mi
3200: 6e 4c 6f 63 61 6c 20 6f 72 20 42 74 53 68 61 72  nLocal or BtShar
3210: 65 64 2e 6d 69 6e 4c 65 61 66 20 2a 2f 0a 20 20  ed.minLeaf */.  
3220: 75 31 36 20 63 65 6c 6c 4f 66 66 73 65 74 3b 20  u16 cellOffset; 
3230: 20 20 20 20 20 2f 2a 20 49 6e 64 65 78 20 69 6e       /* Index in
3240: 20 61 44 61 74 61 20 6f 66 20 66 69 72 73 74 20   aData of first 
3250: 63 65 6c 6c 20 70 6f 69 6e 74 65 72 20 2a 2f 0a  cell pointer */.
3260: 20 20 75 31 36 20 69 64 78 50 61 72 65 6e 74 3b    u16 idxParent;
3270: 20 20 20 20 20 20 20 2f 2a 20 49 6e 64 65 78 20         /* Index 
3280: 69 6e 20 70 61 72 65 6e 74 20 6f 66 20 74 68 69  in parent of thi
3290: 73 20 6e 6f 64 65 20 2a 2f 0a 20 20 75 31 36 20  s node */.  u16 
32a0: 6e 46 72 65 65 3b 20 20 20 20 20 20 20 20 20 20  nFree;          
32b0: 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 66 72   /* Number of fr
32c0: 65 65 20 62 79 74 65 73 20 6f 6e 20 74 68 65 20  ee bytes on the 
32d0: 70 61 67 65 20 2a 2f 0a 20 20 75 31 36 20 6e 43  page */.  u16 nC
32e0: 65 6c 6c 3b 20 20 20 20 20 20 20 20 20 20 20 2f  ell;           /
32f0: 2a 20 4e 75 6d 62 65 72 20 6f 66 20 63 65 6c 6c  * Number of cell
3300: 73 20 6f 6e 20 74 68 69 73 20 70 61 67 65 2c 20  s on this page, 
3310: 6c 6f 63 61 6c 20 61 6e 64 20 6f 76 66 6c 20 2a  local and ovfl *
3320: 2f 0a 20 20 73 74 72 75 63 74 20 5f 4f 76 66 6c  /.  struct _Ovfl
3330: 43 65 6c 6c 20 7b 20 20 20 2f 2a 20 43 65 6c 6c  Cell {   /* Cell
3340: 73 20 74 68 61 74 20 77 69 6c 6c 20 6e 6f 74 20  s that will not 
3350: 66 69 74 20 6f 6e 20 61 44 61 74 61 5b 5d 20 2a  fit on aData[] *
3360: 2f 0a 20 20 20 20 75 38 20 2a 70 43 65 6c 6c 3b  /.    u8 *pCell;
3370: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 50 6f 69            /* Poi
3380: 6e 74 65 72 73 20 74 6f 20 74 68 65 20 62 6f 64  nters to the bod
3390: 79 20 6f 66 20 74 68 65 20 6f 76 65 72 66 6c 6f  y of the overflo
33a0: 77 20 63 65 6c 6c 20 2a 2f 0a 20 20 20 20 75 31  w cell */.    u1
33b0: 36 20 69 64 78 3b 20 20 20 20 20 20 20 20 20 20  6 idx;          
33c0: 20 20 2f 2a 20 49 6e 73 65 72 74 20 74 68 69 73    /* Insert this
33d0: 20 63 65 6c 6c 20 62 65 66 6f 72 65 20 69 64 78   cell before idx
33e0: 2d 74 68 20 6e 6f 6e 2d 6f 76 65 72 66 6c 6f 77  -th non-overflow
33f0: 20 63 65 6c 6c 20 2a 2f 0a 20 20 7d 20 61 4f 76   cell */.  } aOv
3400: 66 6c 5b 35 5d 3b 0a 20 20 42 74 53 68 61 72 65  fl[5];.  BtShare
3410: 64 20 2a 70 42 74 3b 20 20 20 20 20 20 20 2f 2a  d *pBt;       /*
3420: 20 50 6f 69 6e 74 65 72 20 74 6f 20 42 74 53 68   Pointer to BtSh
3430: 61 72 65 64 20 74 68 61 74 20 74 68 69 73 20 70  ared that this p
3440: 61 67 65 20 69 73 20 70 61 72 74 20 6f 66 20 2a  age is part of *
3450: 2f 0a 20 20 75 38 20 2a 61 44 61 74 61 3b 20 20  /.  u8 *aData;  
3460: 20 20 20 20 20 20 20 20 20 2f 2a 20 50 6f 69 6e           /* Poin
3470: 74 65 72 20 74 6f 20 64 69 73 6b 20 69 6d 61 67  ter to disk imag
3480: 65 20 6f 66 20 74 68 65 20 70 61 67 65 20 64 61  e of the page da
3490: 74 61 20 2a 2f 0a 20 20 44 62 50 61 67 65 20 2a  ta */.  DbPage *
34a0: 70 44 62 50 61 67 65 3b 20 20 20 20 20 2f 2a 20  pDbPage;     /* 
34b0: 50 61 67 65 72 20 70 61 67 65 20 68 61 6e 64 6c  Pager page handl
34c0: 65 20 2a 2f 0a 20 20 50 67 6e 6f 20 70 67 6e 6f  e */.  Pgno pgno
34d0: 3b 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 50  ;           /* P
34e0: 61 67 65 20 6e 75 6d 62 65 72 20 66 6f 72 20 74  age number for t
34f0: 68 69 73 20 70 61 67 65 20 2a 2f 0a 20 20 4d 65  his page */.  Me
3500: 6d 50 61 67 65 20 2a 70 50 61 72 65 6e 74 3b 20  mPage *pParent; 
3510: 20 20 20 2f 2a 20 54 68 65 20 70 61 72 65 6e 74     /* The parent
3520: 20 6f 66 20 74 68 69 73 20 70 61 67 65 2e 20 20   of this page.  
3530: 4e 55 4c 4c 20 66 6f 72 20 72 6f 6f 74 20 2a 2f  NULL for root */
3540: 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 20 69  .};../*.** The i
3550: 6e 2d 6d 65 6d 6f 72 79 20 69 6d 61 67 65 20 6f  n-memory image o
3560: 66 20 61 20 64 69 73 6b 20 70 61 67 65 20 68 61  f a disk page ha
3570: 73 20 74 68 65 20 61 75 78 69 6c 69 61 72 79 20  s the auxiliary 
3580: 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 61 70 70 65  information appe
3590: 6e 64 65 64 0a 2a 2a 20 74 6f 20 74 68 65 20 65  nded.** to the e
35a0: 6e 64 2e 20 20 45 58 54 52 41 5f 53 49 5a 45 20  nd.  EXTRA_SIZE 
35b0: 69 73 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66  is the number of
35c0: 20 62 79 74 65 73 20 6f 66 20 73 70 61 63 65 20   bytes of space 
35d0: 6e 65 65 64 65 64 20 74 6f 20 68 6f 6c 64 0a 2a  needed to hold.*
35e0: 2a 20 74 68 61 74 20 65 78 74 72 61 20 69 6e 66  * that extra inf
35f0: 6f 72 6d 61 74 69 6f 6e 2e 0a 2a 2f 0a 23 64 65  ormation..*/.#de
3600: 66 69 6e 65 20 45 58 54 52 41 5f 53 49 5a 45 20  fine EXTRA_SIZE 
3610: 73 69 7a 65 6f 66 28 4d 65 6d 50 61 67 65 29 0a  sizeof(MemPage).
3620: 0a 2f 2a 20 41 20 42 74 72 65 65 20 68 61 6e 64  ./* A Btree hand
3630: 6c 65 0a 2a 2a 0a 2a 2a 20 41 20 64 61 74 61 62  le.**.** A datab
3640: 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 20 63  ase connection c
3650: 6f 6e 74 61 69 6e 73 20 61 20 70 6f 69 6e 74 65  ontains a pointe
3660: 72 20 74 6f 20 61 6e 20 69 6e 73 74 61 6e 63 65  r to an instance
3670: 20 6f 66 0a 2a 2a 20 74 68 69 73 20 6f 62 6a 65   of.** this obje
3680: 63 74 20 66 6f 72 20 65 76 65 72 79 20 64 61 74  ct for every dat
3690: 61 62 61 73 65 20 66 69 6c 65 20 74 68 61 74 20  abase file that 
36a0: 69 74 20 68 61 73 20 6f 70 65 6e 2e 20 20 54 68  it has open.  Th
36b0: 69 73 20 73 74 72 75 63 74 75 72 65 0a 2a 2a 20  is structure.** 
36c0: 69 73 20 6f 70 61 71 75 65 20 74 6f 20 74 68 65  is opaque to the
36d0: 20 64 61 74 61 62 61 73 65 20 63 6f 6e 6e 65 63   database connec
36e0: 74 69 6f 6e 2e 20 20 54 68 65 20 64 61 74 61 62  tion.  The datab
36f0: 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 20 63  ase connection c
3700: 61 6e 6e 6f 74 0a 2a 2a 20 73 65 65 20 74 68 65  annot.** see the
3710: 20 69 6e 74 65 72 6e 61 6c 73 20 6f 66 20 74 68   internals of th
3720: 69 73 20 73 74 72 75 63 74 75 72 65 20 61 6e 64  is structure and
3730: 20 6f 6e 6c 79 20 64 65 61 6c 73 20 77 69 74 68   only deals with
3740: 20 70 6f 69 6e 74 65 72 73 20 74 6f 0a 2a 2a 20   pointers to.** 
3750: 74 68 69 73 20 73 74 72 75 63 74 75 72 65 2e 0a  this structure..
3760: 2a 2a 0a 2a 2a 20 46 6f 72 20 73 6f 6d 65 20 64  **.** For some d
3770: 61 74 61 62 61 73 65 20 66 69 6c 65 73 2c 20 74  atabase files, t
3780: 68 65 20 73 61 6d 65 20 75 6e 64 65 72 6c 79 69  he same underlyi
3790: 6e 67 20 64 61 74 61 62 61 73 65 20 63 61 63 68  ng database cach
37a0: 65 20 6d 69 67 68 74 20 62 65 20 0a 2a 2a 20 73  e might be .** s
37b0: 68 61 72 65 64 20 62 65 74 77 65 65 6e 20 6d 75  hared between mu
37c0: 6c 74 69 70 6c 65 20 63 6f 6e 6e 65 63 74 69 6f  ltiple connectio
37d0: 6e 73 2e 20 20 49 6e 20 74 68 61 74 20 63 61 73  ns.  In that cas
37e0: 65 2c 20 65 61 63 68 20 63 6f 6e 74 65 63 74 69  e, each contecti
37f0: 6f 6e 0a 2a 2a 20 68 61 73 20 69 74 20 6f 77 6e  on.** has it own
3800: 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 69 73   pointer to this
3810: 20 6f 62 6a 65 63 74 2e 20 20 42 75 74 20 65 61   object.  But ea
3820: 63 68 20 69 6e 73 74 61 6e 63 65 20 6f 66 20 74  ch instance of t
3830: 68 69 73 20 6f 62 6a 65 63 74 0a 2a 2a 20 70 6f  his object.** po
3840: 69 6e 74 73 20 74 6f 20 74 68 65 20 73 61 6d 65  ints to the same
3850: 20 42 74 53 68 61 72 65 64 20 6f 62 6a 65 63 74   BtShared object
3860: 2e 20 20 54 68 65 20 64 61 74 61 62 61 73 65 20  .  The database 
3870: 63 61 63 68 65 20 61 6e 64 20 74 68 65 0a 2a 2a  cache and the.**
3880: 20 73 63 68 65 6d 61 20 61 73 73 6f 63 69 61 74   schema associat
3890: 65 64 20 77 69 74 68 20 74 68 65 20 64 61 74 61  ed with the data
38a0: 62 61 73 65 20 66 69 6c 65 20 61 72 65 20 61 6c  base file are al
38b0: 6c 20 63 6f 6e 74 61 69 6e 65 64 20 77 69 74 68  l contained with
38c0: 69 6e 0a 2a 2a 20 74 68 65 20 42 74 53 68 61 72  in.** the BtShar
38d0: 65 64 20 6f 62 6a 65 63 74 2e 0a 2a 2a 0a 2a 2a  ed object..**.**
38e0: 20 41 6c 6c 20 66 69 65 6c 64 73 20 69 6e 20 74   All fields in t
38f0: 68 69 73 20 73 74 72 75 63 74 75 72 65 20 61 72  his structure ar
3900: 65 20 61 63 63 65 73 73 65 64 20 75 6e 64 65 72  e accessed under
3910: 20 74 68 65 20 73 71 6c 69 74 65 33 2e 6d 75 74   the sqlite3.mut
3920: 65 78 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 42 74  ex..*/.struct Bt
3930: 72 65 65 20 7b 0a 20 20 73 71 6c 69 74 65 33 20  ree {.  sqlite3 
3940: 2a 70 53 71 6c 69 74 65 3b 20 20 2f 2a 20 54 68  *pSqlite;  /* Th
3950: 65 20 64 61 74 61 62 61 73 65 20 63 6f 6e 6e 65  e database conne
3960: 63 74 69 6f 6e 20 68 6f 6c 64 69 6e 67 20 74 68  ction holding th
3970: 69 73 20 62 74 72 65 65 20 2a 2f 0a 20 20 42 74  is btree */.  Bt
3980: 53 68 61 72 65 64 20 2a 70 42 74 3b 20 20 20 20  Shared *pBt;    
3990: 20 2f 2a 20 53 68 61 72 61 62 6c 65 20 63 6f 6e   /* Sharable con
39a0: 74 65 6e 74 20 6f 66 20 74 68 69 73 20 62 74 72  tent of this btr
39b0: 65 65 20 2a 2f 0a 20 20 75 38 20 69 6e 54 72 61  ee */.  u8 inTra
39c0: 6e 73 3b 20 20 20 20 20 20 20 20 2f 2a 20 54 52  ns;        /* TR
39d0: 41 4e 53 5f 4e 4f 4e 45 2c 20 54 52 41 4e 53 5f  ANS_NONE, TRANS_
39e0: 52 45 41 44 20 6f 72 20 54 52 41 4e 53 5f 57 52  READ or TRANS_WR
39f0: 49 54 45 20 2a 2f 0a 20 20 75 38 20 73 68 61 72  ITE */.  u8 shar
3a00: 61 62 6c 65 3b 20 20 20 20 20 20 20 2f 2a 20 54  able;       /* T
3a10: 72 75 65 20 69 66 20 77 65 20 63 61 6e 20 73 68  rue if we can sh
3a20: 61 72 65 20 70 42 74 20 77 69 74 68 20 6f 74 68  are pBt with oth
3a30: 65 72 20 70 53 71 6c 69 74 65 20 2a 2f 0a 20 20  er pSqlite */.  
3a40: 75 38 20 6c 6f 63 6b 65 64 3b 20 20 20 20 20 20  u8 locked;      
3a50: 20 20 20 2f 2a 20 54 72 75 65 20 69 66 20 70 53     /* True if pS
3a60: 71 6c 69 74 65 20 63 75 72 72 65 6e 74 6c 79 20  qlite currently 
3a70: 68 61 73 20 70 42 74 20 6c 6f 63 6b 65 64 20 2a  has pBt locked *
3a80: 2f 0a 20 20 69 6e 74 20 77 61 6e 74 54 6f 4c 6f  /.  int wantToLo
3a90: 63 6b 3b 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72  ck;    /* Number
3aa0: 20 6f 66 20 6e 65 73 74 65 64 20 63 61 6c 6c 73   of nested calls
3ab0: 20 74 6f 20 73 71 6c 69 74 65 33 42 74 72 65 65   to sqlite3Btree
3ac0: 45 6e 74 65 72 28 29 20 2a 2f 0a 20 20 42 74 72  Enter() */.  Btr
3ad0: 65 65 20 2a 70 4e 65 78 74 3b 20 20 20 20 20 20  ee *pNext;      
3ae0: 2f 2a 20 4c 69 73 74 20 6f 66 20 42 74 72 65 65  /* List of Btree
3af0: 73 20 77 69 74 68 20 74 68 65 20 73 61 6d 65 20  s with the same 
3b00: 70 53 71 6c 69 74 65 20 76 61 6c 75 65 20 2a 2f  pSqlite value */
3b10: 0a 20 20 42 74 72 65 65 20 2a 70 50 72 65 76 3b  .  Btree *pPrev;
3b20: 20 20 20 20 20 20 2f 2a 20 42 61 63 6b 20 70 6f        /* Back po
3b30: 69 6e 74 65 72 20 6f 66 20 74 68 65 20 73 61 6d  inter of the sam
3b40: 65 20 6c 69 73 74 20 2a 2f 0a 7d 3b 0a 0a 2f 2a  e list */.};../*
3b50: 0a 2a 2a 20 42 74 72 65 65 2e 69 6e 54 72 61 6e  .** Btree.inTran
3b60: 73 20 6d 61 79 20 74 61 6b 65 20 6f 6e 65 20 6f  s may take one o
3b70: 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20  f the following 
3b80: 76 61 6c 75 65 73 2e 0a 2a 2a 0a 2a 2a 20 49 66  values..**.** If
3b90: 20 74 68 65 20 73 68 61 72 65 64 2d 64 61 74 61   the shared-data
3ba0: 20 65 78 74 65 6e 73 69 6f 6e 20 69 73 20 65 6e   extension is en
3bb0: 61 62 6c 65 64 2c 20 74 68 65 72 65 20 6d 61 79  abled, there may
3bc0: 20 62 65 20 6d 75 6c 74 69 70 6c 65 20 75 73 65   be multiple use
3bd0: 72 73 0a 2a 2a 20 6f 66 20 74 68 65 20 42 74 72  rs.** of the Btr
3be0: 65 65 20 73 74 72 75 63 74 75 72 65 2e 20 41 74  ee structure. At
3bf0: 20 6d 6f 73 74 20 6f 6e 65 20 6f 66 20 74 68 65   most one of the
3c00: 73 65 20 6d 61 79 20 6f 70 65 6e 20 61 20 77 72  se may open a wr
3c10: 69 74 65 20 74 72 61 6e 73 61 63 74 69 6f 6e 2c  ite transaction,
3c20: 0a 2a 2a 20 62 75 74 20 61 6e 79 20 6e 75 6d 62  .** but any numb
3c30: 65 72 20 6d 61 79 20 68 61 76 65 20 61 63 74 69  er may have acti
3c40: 76 65 20 72 65 61 64 20 74 72 61 6e 73 61 63 74  ve read transact
3c50: 69 6f 6e 73 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65  ions..*/.#define
3c60: 20 54 52 41 4e 53 5f 4e 4f 4e 45 20 20 30 0a 23   TRANS_NONE  0.#
3c70: 64 65 66 69 6e 65 20 54 52 41 4e 53 5f 52 45 41  define TRANS_REA
3c80: 44 20 20 31 0a 23 64 65 66 69 6e 65 20 54 52 41  D  1.#define TRA
3c90: 4e 53 5f 57 52 49 54 45 20 32 0a 0a 2f 2a 0a 2a  NS_WRITE 2../*.*
3ca0: 2a 20 41 6e 20 69 6e 73 74 61 6e 63 65 20 6f 66  * An instance of
3cb0: 20 74 68 69 73 20 6f 62 6a 65 63 74 20 72 65 70   this object rep
3cc0: 72 65 73 65 6e 74 73 20 61 20 73 69 6e 67 6c 65  resents a single
3cd0: 20 64 61 74 61 62 61 73 65 20 66 69 6c 65 2e 0a   database file..
3ce0: 2a 2a 20 0a 2a 2a 20 41 20 73 69 6e 67 6c 65 20  ** .** A single 
3cf0: 64 61 74 61 62 61 73 65 20 66 69 6c 65 20 63 61  database file ca
3d00: 6e 20 62 65 20 69 6e 20 75 73 65 20 61 73 20 74  n be in use as t
3d10: 68 65 20 73 61 6d 65 20 74 69 6d 65 20 62 79 20  he same time by 
3d20: 74 77 6f 0a 2a 2a 20 6f 72 20 6d 6f 72 65 20 64  two.** or more d
3d30: 61 74 61 62 61 73 65 20 63 6f 6e 6e 65 63 74 69  atabase connecti
3d40: 6f 6e 73 2e 20 20 57 68 65 6e 20 74 77 6f 20 6f  ons.  When two o
3d50: 72 20 6d 6f 72 65 20 63 6f 6e 6e 65 63 74 69 6f  r more connectio
3d60: 6e 73 20 61 72 65 0a 2a 2a 20 73 68 61 72 69 6e  ns are.** sharin
3d70: 67 20 74 68 65 20 73 61 6d 65 20 64 61 74 61 62  g the same datab
3d80: 61 73 65 20 66 69 6c 65 2c 20 65 61 63 68 20 63  ase file, each c
3d90: 6f 6e 6e 65 63 74 69 6f 6e 20 68 61 73 20 69 74  onnection has it
3da0: 20 6f 77 6e 0a 2a 2a 20 70 72 69 76 61 74 65 20   own.** private 
3db0: 42 74 72 65 65 20 6f 62 6a 65 63 74 20 66 6f 72  Btree object for
3dc0: 20 74 68 65 20 66 69 6c 65 20 61 6e 64 20 65 61   the file and ea
3dd0: 63 68 20 6f 66 20 74 68 6f 73 65 20 42 74 72 65  ch of those Btre
3de0: 65 73 20 70 6f 69 6e 74 73 0a 2a 2a 20 74 6f 20  es points.** to 
3df0: 74 68 69 73 20 6f 6e 65 20 42 74 53 68 61 72 65  this one BtShare
3e00: 64 20 6f 62 6a 65 63 74 2e 20 20 42 74 53 68 61  d object.  BtSha
3e10: 72 65 64 2e 6e 52 65 66 20 69 73 20 74 68 65 20  red.nRef is the 
3e20: 6e 75 6d 62 65 72 20 6f 66 0a 2a 2a 20 63 6f 6e  number of.** con
3e30: 6e 65 63 74 69 6f 6e 73 20 63 75 72 72 65 6e 74  nections current
3e40: 6c 79 20 73 68 61 72 69 6e 67 20 74 68 69 73 20  ly sharing this 
3e50: 64 61 74 61 62 61 73 65 20 66 69 6c 65 2e 0a 2a  database file..*
3e60: 2a 0a 2a 2a 20 46 69 65 6c 64 73 20 69 6e 20 74  *.** Fields in t
3e70: 68 69 73 20 73 74 72 75 63 74 75 72 65 20 61 72  his structure ar
3e80: 65 20 61 63 63 65 73 73 65 64 20 75 6e 64 65 72  e accessed under
3e90: 20 74 68 65 20 42 74 53 68 61 72 65 64 2e 6d 75   the BtShared.mu
3ea0: 74 65 78 0a 2a 2a 20 6d 75 74 65 78 2c 20 65 78  tex.** mutex, ex
3eb0: 63 65 70 74 20 66 6f 72 20 6e 52 65 66 20 61 6e  cept for nRef an
3ec0: 64 20 70 4e 65 78 74 20 77 68 69 63 68 20 61 72  d pNext which ar
3ed0: 65 20 61 63 63 65 73 73 65 64 20 75 6e 64 65 72  e accessed under
3ee0: 20 74 68 65 0a 2a 2a 20 67 6c 6f 62 61 6c 20 53   the.** global S
3ef0: 51 4c 49 54 45 5f 4d 55 54 45 58 5f 53 54 41 54  QLITE_MUTEX_STAT
3f00: 49 43 5f 4d 41 53 54 45 52 20 6d 75 74 65 78 2e  IC_MASTER mutex.
3f10: 0a 2a 2f 0a 73 74 72 75 63 74 20 42 74 53 68 61  .*/.struct BtSha
3f20: 72 65 64 20 7b 0a 20 20 50 61 67 65 72 20 2a 70  red {.  Pager *p
3f30: 50 61 67 65 72 3b 20 20 20 20 20 20 20 20 2f 2a  Pager;        /*
3f40: 20 54 68 65 20 70 61 67 65 20 63 61 63 68 65 20   The page cache 
3f50: 2a 2f 0a 20 20 42 74 43 75 72 73 6f 72 20 2a 70  */.  BtCursor *p
3f60: 43 75 72 73 6f 72 3b 20 20 20 20 2f 2a 20 41 20  Cursor;    /* A 
3f70: 6c 69 73 74 20 6f 66 20 61 6c 6c 20 6f 70 65 6e  list of all open
3f80: 20 63 75 72 73 6f 72 73 20 2a 2f 0a 20 20 4d 65   cursors */.  Me
3f90: 6d 50 61 67 65 20 2a 70 50 61 67 65 31 3b 20 20  mPage *pPage1;  
3fa0: 20 20 20 20 2f 2a 20 46 69 72 73 74 20 70 61 67      /* First pag
3fb0: 65 20 6f 66 20 74 68 65 20 64 61 74 61 62 61 73  e of the databas
3fc0: 65 20 2a 2f 0a 20 20 75 38 20 69 6e 53 74 6d 74  e */.  u8 inStmt
3fd0: 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20  ;            /* 
3fe0: 54 72 75 65 20 69 66 20 77 65 20 61 72 65 20 69  True if we are i
3ff0: 6e 20 61 20 73 74 61 74 65 6d 65 6e 74 20 73 75  n a statement su
4000: 62 74 72 61 6e 73 61 63 74 69 6f 6e 20 2a 2f 0a  btransaction */.
4010: 20 20 75 38 20 72 65 61 64 4f 6e 6c 79 3b 20 20    u8 readOnly;  
4020: 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20          /* True 
4030: 69 66 20 74 68 65 20 75 6e 64 65 72 6c 79 69 6e  if the underlyin
4040: 67 20 66 69 6c 65 20 69 73 20 72 65 61 64 6f 6e  g file is readon
4050: 6c 79 20 2a 2f 0a 20 20 75 38 20 6d 61 78 45 6d  ly */.  u8 maxEm
4060: 62 65 64 46 72 61 63 3b 20 20 20 20 20 20 2f 2a  bedFrac;      /*
4070: 20 4d 61 78 69 6d 75 6d 20 70 61 79 6c 6f 61 64   Maximum payload
4080: 20 61 73 20 25 20 6f 66 20 74 6f 74 61 6c 20 70   as % of total p
4090: 61 67 65 20 73 69 7a 65 20 2a 2f 0a 20 20 75 38  age size */.  u8
40a0: 20 6d 69 6e 45 6d 62 65 64 46 72 61 63 3b 20 20   minEmbedFrac;  
40b0: 20 20 20 20 2f 2a 20 4d 69 6e 69 6d 75 6d 20 70      /* Minimum p
40c0: 61 79 6c 6f 61 64 20 61 73 20 25 20 6f 66 20 74  ayload as % of t
40d0: 6f 74 61 6c 20 70 61 67 65 20 73 69 7a 65 20 2a  otal page size *
40e0: 2f 0a 20 20 75 38 20 6d 69 6e 4c 65 61 66 46 72  /.  u8 minLeafFr
40f0: 61 63 3b 20 20 20 20 20 20 20 2f 2a 20 4d 69 6e  ac;       /* Min
4100: 69 6d 75 6d 20 6c 65 61 66 20 70 61 79 6c 6f 61  imum leaf payloa
4110: 64 20 61 73 20 25 20 6f 66 20 74 6f 74 61 6c 20  d as % of total 
4120: 70 61 67 65 20 73 69 7a 65 20 2a 2f 0a 20 20 75  page size */.  u
4130: 38 20 70 61 67 65 53 69 7a 65 46 69 78 65 64 3b  8 pageSizeFixed;
4140: 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69 66 20       /* True if 
4150: 74 68 65 20 70 61 67 65 20 73 69 7a 65 20 63 61  the page size ca
4160: 6e 20 6e 6f 20 6c 6f 6e 67 65 72 20 62 65 20 63  n no longer be c
4170: 68 61 6e 67 65 64 20 2a 2f 0a 23 69 66 6e 64 65  hanged */.#ifnde
4180: 66 20 53 51 4c 49 54 45 5f 4f 4d 49 54 5f 41 55  f SQLITE_OMIT_AU
4190: 54 4f 56 41 43 55 55 4d 0a 20 20 75 38 20 61 75  TOVACUUM.  u8 au
41a0: 74 6f 56 61 63 75 75 6d 3b 20 20 20 20 20 20 20  toVacuum;       
41b0: 20 2f 2a 20 54 72 75 65 20 69 66 20 61 75 74 6f   /* True if auto
41c0: 2d 76 61 63 75 75 6d 20 69 73 20 65 6e 61 62 6c  -vacuum is enabl
41d0: 65 64 20 2a 2f 0a 20 20 75 38 20 69 6e 63 72 56  ed */.  u8 incrV
41e0: 61 63 75 75 6d 3b 20 20 20 20 20 20 20 20 2f 2a  acuum;        /*
41f0: 20 54 72 75 65 20 69 66 20 69 6e 63 72 2d 76 61   True if incr-va
4200: 63 75 75 6d 20 69 73 20 65 6e 61 62 6c 65 64 20  cuum is enabled 
4210: 2a 2f 0a 20 20 50 67 6e 6f 20 6e 54 72 75 6e 63  */.  Pgno nTrunc
4220: 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 6f  ;          /* No
4230: 6e 2d 7a 65 72 6f 20 69 66 20 74 68 65 20 64 62  n-zero if the db
4240: 20 77 69 6c 6c 20 62 65 20 74 72 75 6e 63 61 74   will be truncat
4250: 65 64 20 28 69 6e 63 72 20 76 61 63 75 75 6d 29  ed (incr vacuum)
4260: 20 2a 2f 0a 23 65 6e 64 69 66 0a 20 20 75 31 36   */.#endif.  u16
4270: 20 70 61 67 65 53 69 7a 65 3b 20 20 20 20 20 20   pageSize;      
4280: 20 20 20 2f 2a 20 54 6f 74 61 6c 20 6e 75 6d 62     /* Total numb
4290: 65 72 20 6f 66 20 62 79 74 65 73 20 6f 6e 20 61  er of bytes on a
42a0: 20 70 61 67 65 20 2a 2f 0a 20 20 75 31 36 20 75   page */.  u16 u
42b0: 73 61 62 6c 65 53 69 7a 65 3b 20 20 20 20 20 20  sableSize;      
42c0: 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 75 73   /* Number of us
42d0: 61 62 6c 65 20 62 79 74 65 73 20 6f 6e 20 65 61  able bytes on ea
42e0: 63 68 20 70 61 67 65 20 2a 2f 0a 20 20 69 6e 74  ch page */.  int
42f0: 20 6d 61 78 4c 6f 63 61 6c 3b 20 20 20 20 20 20   maxLocal;      
4300: 20 20 20 2f 2a 20 4d 61 78 69 6d 75 6d 20 6c 6f     /* Maximum lo
4310: 63 61 6c 20 70 61 79 6c 6f 61 64 20 69 6e 20 6e  cal payload in n
4320: 6f 6e 2d 4c 45 41 46 44 41 54 41 20 74 61 62 6c  on-LEAFDATA tabl
4330: 65 73 20 2a 2f 0a 20 20 69 6e 74 20 6d 69 6e 4c  es */.  int minL
4340: 6f 63 61 6c 3b 20 20 20 20 20 20 20 20 20 2f 2a  ocal;         /*
4350: 20 4d 69 6e 69 6d 75 6d 20 6c 6f 63 61 6c 20 70   Minimum local p
4360: 61 79 6c 6f 61 64 20 69 6e 20 6e 6f 6e 2d 4c 45  ayload in non-LE
4370: 41 46 44 41 54 41 20 74 61 62 6c 65 73 20 2a 2f  AFDATA tables */
4380: 0a 20 20 69 6e 74 20 6d 61 78 4c 65 61 66 3b 20  .  int maxLeaf; 
4390: 20 20 20 20 20 20 20 20 20 2f 2a 20 4d 61 78 69           /* Maxi
43a0: 6d 75 6d 20 6c 6f 63 61 6c 20 70 61 79 6c 6f 61  mum local payloa
43b0: 64 20 69 6e 20 61 20 4c 45 41 46 44 41 54 41 20  d in a LEAFDATA 
43c0: 74 61 62 6c 65 20 2a 2f 0a 20 20 69 6e 74 20 6d  table */.  int m
43d0: 69 6e 4c 65 61 66 3b 20 20 20 20 20 20 20 20 20  inLeaf;         
43e0: 20 2f 2a 20 4d 69 6e 69 6d 75 6d 20 6c 6f 63 61   /* Minimum loca
43f0: 6c 20 70 61 79 6c 6f 61 64 20 69 6e 20 61 20 4c  l payload in a L
4400: 45 41 46 44 41 54 41 20 74 61 62 6c 65 20 2a 2f  EAFDATA table */
4410: 0a 20 20 42 75 73 79 48 61 6e 64 6c 65 72 20 2a  .  BusyHandler *
4420: 70 42 75 73 79 48 61 6e 64 6c 65 72 3b 20 20 20  pBusyHandler;   
4430: 2f 2a 20 43 61 6c 6c 62 61 63 6b 20 66 6f 72 20  /* Callback for 
4440: 77 68 65 6e 20 74 68 65 72 65 20 69 73 20 6c 6f  when there is lo
4450: 63 6b 20 63 6f 6e 74 65 6e 74 69 6f 6e 20 2a 2f  ck contention */
4460: 0a 20 20 75 38 20 69 6e 54 72 61 6e 73 61 63 74  .  u8 inTransact
4470: 69 6f 6e 3b 20 20 20 20 20 2f 2a 20 54 72 61 6e  ion;     /* Tran
4480: 73 61 63 74 69 6f 6e 20 73 74 61 74 65 20 2a 2f  saction state */
4490: 0a 20 20 69 6e 74 20 6e 54 72 61 6e 73 61 63 74  .  int nTransact
44a0: 69 6f 6e 3b 20 20 20 20 20 2f 2a 20 4e 75 6d 62  ion;     /* Numb
44b0: 65 72 20 6f 66 20 6f 70 65 6e 20 74 72 61 6e 73  er of open trans
44c0: 61 63 74 69 6f 6e 73 20 28 72 65 61 64 20 2b 20  actions (read + 
44d0: 77 72 69 74 65 29 20 2a 2f 0a 20 20 76 6f 69 64  write) */.  void
44e0: 20 2a 70 53 63 68 65 6d 61 3b 20 20 20 20 20 20   *pSchema;      
44f0: 20 20 2f 2a 20 50 6f 69 6e 74 65 72 20 74 6f 20    /* Pointer to 
4500: 73 70 61 63 65 20 61 6c 6c 6f 63 61 74 65 64 20  space allocated 
4510: 62 79 20 73 71 6c 69 74 65 33 42 74 72 65 65 53  by sqlite3BtreeS
4520: 63 68 65 6d 61 28 29 20 2a 2f 0a 20 20 76 6f 69  chema() */.  voi
4530: 64 20 28 2a 78 46 72 65 65 53 63 68 65 6d 61 29  d (*xFreeSchema)
4540: 28 76 6f 69 64 2a 29 3b 20 20 2f 2a 20 44 65 73  (void*);  /* Des
4550: 74 72 75 63 74 6f 72 20 66 6f 72 20 42 74 53 68  tructor for BtSh
4560: 61 72 65 64 2e 70 53 63 68 65 6d 61 20 2a 2f 0a  ared.pSchema */.
4570: 23 69 66 6e 64 65 66 20 53 51 4c 49 54 45 5f 4f  #ifndef SQLITE_O
4580: 4d 49 54 5f 53 48 41 52 45 44 5f 43 41 43 48 45  MIT_SHARED_CACHE
4590: 0a 20 20 69 6e 74 20 6e 52 65 66 3b 20 20 20 20  .  int nRef;    
45a0: 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62           /* Numb
45b0: 65 72 20 6f 66 20 72 65 66 65 72 65 6e 63 65 73  er of references
45c0: 20 74 6f 20 74 68 69 73 20 73 74 72 75 63 74 75   to this structu
45d0: 72 65 20 2a 2f 0a 20 20 42 74 53 68 61 72 65 64  re */.  BtShared
45e0: 20 2a 70 4e 65 78 74 3b 20 20 20 20 20 20 2f 2a   *pNext;      /*
45f0: 20 4e 65 78 74 20 6f 6e 20 61 20 6c 69 73 74 20   Next on a list 
4600: 6f 66 20 73 68 61 72 61 62 6c 65 20 42 74 53 68  of sharable BtSh
4610: 61 72 65 64 20 73 74 72 75 63 74 73 20 2a 2f 0a  ared structs */.
4620: 20 20 73 71 6c 69 74 65 33 5f 6d 75 74 65 78 20    sqlite3_mutex 
4630: 2a 6d 75 74 65 78 3b 20 2f 2a 20 4e 6f 6e 2d 72  *mutex; /* Non-r
4640: 65 63 75 72 73 69 76 65 20 6d 75 74 65 78 20 72  ecursive mutex r
4650: 65 71 75 69 72 65 64 20 74 6f 20 61 63 63 65 73  equired to acces
4660: 73 20 74 68 69 73 20 73 74 72 75 63 74 20 2a 2f  s this struct */
4670: 0a 20 20 42 74 4c 6f 63 6b 20 2a 70 4c 6f 63 6b  .  BtLock *pLock
4680: 3b 20 20 20 20 20 20 20 20 2f 2a 20 4c 69 73 74  ;        /* List
4690: 20 6f 66 20 6c 6f 63 6b 73 20 68 65 6c 64 20 6f   of locks held o
46a0: 6e 20 74 68 69 73 20 73 68 61 72 65 64 2d 62 74  n this shared-bt
46b0: 72 65 65 20 73 74 72 75 63 74 20 2a 2f 0a 23 65  ree struct */.#e
46c0: 6e 64 69 66 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 41  ndif.};../*.** A
46d0: 6e 20 69 6e 73 74 61 6e 63 65 20 6f 66 20 74 68  n instance of th
46e0: 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 73 74 72 75  e following stru
46f0: 63 74 75 72 65 20 69 73 20 75 73 65 64 20 74 6f  cture is used to
4700: 20 68 6f 6c 64 20 69 6e 66 6f 72 6d 61 74 69 6f   hold informatio
4710: 6e 0a 2a 2a 20 61 62 6f 75 74 20 61 20 63 65 6c  n.** about a cel
4720: 6c 2e 20 20 54 68 65 20 70 61 72 73 65 43 65 6c  l.  The parseCel
4730: 6c 50 74 72 28 29 20 66 75 6e 63 74 69 6f 6e 20  lPtr() function 
4740: 66 69 6c 6c 73 20 69 6e 20 74 68 69 73 20 73 74  fills in this st
4750: 72 75 63 74 75 72 65 0a 2a 2a 20 62 61 73 65 64  ructure.** based
4760: 20 6f 6e 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20   on information 
4770: 65 78 74 72 61 63 74 20 66 72 6f 6d 20 74 68 65  extract from the
4780: 20 72 61 77 20 64 69 73 6b 20 70 61 67 65 2e 0a   raw disk page..
4790: 2a 2f 0a 74 79 70 65 64 65 66 20 73 74 72 75 63  */.typedef struc
47a0: 74 20 43 65 6c 6c 49 6e 66 6f 20 43 65 6c 6c 49  t CellInfo CellI
47b0: 6e 66 6f 3b 0a 73 74 72 75 63 74 20 43 65 6c 6c  nfo;.struct Cell
47c0: 49 6e 66 6f 20 7b 0a 20 20 75 38 20 2a 70 43 65  Info {.  u8 *pCe
47d0: 6c 6c 3b 20 20 20 20 20 2f 2a 20 50 6f 69 6e 74  ll;     /* Point
47e0: 65 72 20 74 6f 20 74 68 65 20 73 74 61 72 74 20  er to the start 
47f0: 6f 66 20 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 20  of cell content 
4800: 2a 2f 0a 20 20 69 36 34 20 6e 4b 65 79 3b 20 20  */.  i64 nKey;  
4810: 20 20 20 20 2f 2a 20 54 68 65 20 6b 65 79 20 66      /* The key f
4820: 6f 72 20 49 4e 54 4b 45 59 20 74 61 62 6c 65 73  or INTKEY tables
4830: 2c 20 6f 72 20 6e 75 6d 62 65 72 20 6f 66 20 62  , or number of b
4840: 79 74 65 73 20 69 6e 20 6b 65 79 20 2a 2f 0a 20  ytes in key */. 
4850: 20 75 33 32 20 6e 44 61 74 61 3b 20 20 20 20 20   u32 nData;     
4860: 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 62 79 74  /* Number of byt
4870: 65 73 20 6f 66 20 64 61 74 61 20 2a 2f 0a 20 20  es of data */.  
4880: 75 33 32 20 6e 50 61 79 6c 6f 61 64 3b 20 20 2f  u32 nPayload;  /
4890: 2a 20 54 6f 74 61 6c 20 61 6d 6f 75 6e 74 20 6f  * Total amount o
48a0: 66 20 70 61 79 6c 6f 61 64 20 2a 2f 0a 20 20 75  f payload */.  u
48b0: 31 36 20 6e 48 65 61 64 65 72 3b 20 20 20 2f 2a  16 nHeader;   /*
48c0: 20 53 69 7a 65 20 6f 66 20 74 68 65 20 63 65 6c   Size of the cel
48d0: 6c 20 63 6f 6e 74 65 6e 74 20 68 65 61 64 65 72  l content header
48e0: 20 69 6e 20 62 79 74 65 73 20 2a 2f 0a 20 20 75   in bytes */.  u
48f0: 31 36 20 6e 4c 6f 63 61 6c 3b 20 20 20 20 2f 2a  16 nLocal;    /*
4900: 20 41 6d 6f 75 6e 74 20 6f 66 20 70 61 79 6c 6f   Amount of paylo
4910: 61 64 20 68 65 6c 64 20 6c 6f 63 61 6c 6c 79 20  ad held locally 
4920: 2a 2f 0a 20 20 75 31 36 20 69 4f 76 65 72 66 6c  */.  u16 iOverfl
4930: 6f 77 3b 20 2f 2a 20 4f 66 66 73 65 74 20 74 6f  ow; /* Offset to
4940: 20 6f 76 65 72 66 6c 6f 77 20 70 61 67 65 20 6e   overflow page n
4950: 75 6d 62 65 72 2e 20 20 5a 65 72 6f 20 69 66 20  umber.  Zero if 
4960: 6e 6f 20 6f 76 65 72 66 6c 6f 77 20 2a 2f 0a 20  no overflow */. 
4970: 20 75 31 36 20 6e 53 69 7a 65 3b 20 20 20 20 20   u16 nSize;     
4980: 2f 2a 20 53 69 7a 65 20 6f 66 20 74 68 65 20 63  /* Size of the c
4990: 65 6c 6c 20 63 6f 6e 74 65 6e 74 20 6f 6e 20 74  ell content on t
49a0: 68 65 20 6d 61 69 6e 20 62 2d 74 72 65 65 20 70  he main b-tree p
49b0: 61 67 65 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a  age */.};../*.**
49c0: 20 41 20 63 75 72 73 6f 72 20 69 73 20 61 20 70   A cursor is a p
49d0: 6f 69 6e 74 65 72 20 74 6f 20 61 20 70 61 72 74  ointer to a part
49e0: 69 63 75 6c 61 72 20 65 6e 74 72 79 20 77 69 74  icular entry wit
49f0: 68 69 6e 20 61 20 70 61 72 74 69 63 75 6c 61 72  hin a particular
4a00: 0a 2a 2a 20 62 2d 74 72 65 65 20 77 69 74 68 69  .** b-tree withi
4a10: 6e 20 61 20 64 61 74 61 62 61 73 65 20 66 69 6c  n a database fil
4a20: 65 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 65 6e 74  e..**.** The ent
4a30: 72 79 20 69 73 20 69 64 65 6e 74 69 66 69 65 64  ry is identified
4a40: 20 62 79 20 69 74 73 20 4d 65 6d 50 61 67 65 20   by its MemPage 
4a50: 61 6e 64 20 74 68 65 20 69 6e 64 65 78 20 69 6e  and the index in
4a60: 0a 2a 2a 20 4d 65 6d 50 61 67 65 2e 61 43 65 6c  .** MemPage.aCel
4a70: 6c 5b 5d 20 6f 66 20 74 68 65 20 65 6e 74 72 79  l[] of the entry
4a80: 2e 0a 2a 2a 0a 2a 2a 20 57 68 65 6e 20 61 20 73  ..**.** When a s
4a90: 69 6e 67 6c 65 20 64 61 74 61 62 61 73 65 20 66  ingle database f
4aa0: 69 6c 65 20 63 61 6e 20 73 68 61 72 65 64 20 62  ile can shared b
4ab0: 79 20 74 77 6f 20 6d 6f 72 65 20 64 61 74 61 62  y two more datab
4ac0: 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 73 2c  ase connections,
4ad0: 0a 2a 2a 20 62 75 74 20 63 75 72 73 6f 72 73 20  .** but cursors 
4ae0: 63 61 6e 6e 6f 74 20 62 65 20 73 68 61 72 65 64  cannot be shared
4af0: 2e 20 20 45 61 63 68 20 63 75 72 73 6f 72 20 69  .  Each cursor i
4b00: 73 20 61 73 73 6f 63 69 61 74 65 64 20 77 69 74  s associated wit
4b10: 68 20 61 0a 2a 2a 20 70 61 72 74 69 63 75 6c 61  h a.** particula
4b20: 72 20 64 61 74 61 62 61 73 65 20 63 6f 6e 6e 65  r database conne
4b30: 63 74 69 6f 6e 20 69 64 65 6e 74 69 66 69 65 64  ction identified
4b40: 20 42 74 43 75 72 73 6f 72 2e 70 42 74 72 65 65   BtCursor.pBtree
4b50: 2e 70 53 71 6c 69 74 65 2e 0a 2a 2a 0a 2a 2a 20  .pSqlite..**.** 
4b60: 46 69 65 6c 64 73 20 69 6e 20 74 68 69 73 20 73  Fields in this s
4b70: 74 72 75 63 74 75 72 65 20 61 72 65 20 61 63 63  tructure are acc
4b80: 65 73 73 65 64 20 75 6e 64 65 72 20 74 68 65 20  essed under the 
4b90: 42 74 53 68 61 72 65 64 2e 6d 75 74 65 78 0a 2a  BtShared.mutex.*
4ba0: 2a 20 6d 75 74 65 78 2e 20 20 54 68 65 20 70 42  * mutex.  The pB
4bb0: 74 72 65 65 20 66 69 65 6c 64 20 69 73 20 73 61  tree field is sa
4bc0: 66 65 20 74 6f 20 61 63 63 65 73 73 20 75 6e 64  fe to access und
4bd0: 65 72 20 74 68 65 0a 2a 2a 20 42 74 53 68 61 72  er the.** BtShar
4be0: 65 64 2d 3e 70 42 74 72 65 65 2d 3e 70 53 71 6c  ed->pBtree->pSql
4bf0: 69 74 65 2d 3e 6d 75 74 65 78 20 6d 75 74 65 78  ite->mutex mutex
4c00: 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 42 74 43 75  ..*/.struct BtCu
4c10: 72 73 6f 72 20 7b 0a 20 20 42 74 72 65 65 20 2a  rsor {.  Btree *
4c20: 70 42 74 72 65 65 3b 20 20 20 20 20 20 20 20 20  pBtree;         
4c30: 20 20 20 2f 2a 20 54 68 65 20 42 74 72 65 65 20     /* The Btree 
4c40: 74 6f 20 77 68 69 63 68 20 74 68 69 73 20 63 75  to which this cu
4c50: 72 73 6f 72 20 62 65 6c 6f 6e 67 73 20 2a 2f 0a  rsor belongs */.
4c60: 20 20 42 74 43 75 72 73 6f 72 20 2a 70 4e 65 78    BtCursor *pNex
4c70: 74 2c 20 2a 70 50 72 65 76 3b 20 20 2f 2a 20 46  t, *pPrev;  /* F
4c80: 6f 72 6d 73 20 61 20 6c 69 6e 6b 65 64 20 6c 69  orms a linked li
4c90: 73 74 20 6f 66 20 61 6c 6c 20 63 75 72 73 6f 72  st of all cursor
4ca0: 73 20 2a 2f 0a 20 20 69 6e 74 20 28 2a 78 43 6f  s */.  int (*xCo
4cb0: 6d 70 61 72 65 29 28 76 6f 69 64 2a 2c 69 6e 74  mpare)(void*,int
4cc0: 2c 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e 74  ,const void*,int
4cd0: 2c 63 6f 6e 73 74 20 76 6f 69 64 2a 29 3b 20 2f  ,const void*); /
4ce0: 2a 20 4b 65 79 20 63 6f 6d 70 20 66 75 6e 63 20  * Key comp func 
4cf0: 2a 2f 0a 20 20 76 6f 69 64 20 2a 70 41 72 67 3b  */.  void *pArg;
4d00: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f                 /
4d10: 2a 20 46 69 72 73 74 20 61 72 67 20 74 6f 20 78  * First arg to x
4d20: 43 6f 6d 70 61 72 65 28 29 20 2a 2f 0a 20 20 50  Compare() */.  P
4d30: 67 6e 6f 20 70 67 6e 6f 52 6f 6f 74 3b 20 20 20  gno pgnoRoot;   
4d40: 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20           /* The 
4d50: 72 6f 6f 74 20 70 61 67 65 20 6f 66 20 74 68 69  root page of thi
4d60: 73 20 74 72 65 65 20 2a 2f 0a 20 20 4d 65 6d 50  s tree */.  MemP
4d70: 61 67 65 20 2a 70 50 61 67 65 3b 20 20 20 20 20  age *pPage;     
4d80: 20 20 20 20 20 20 2f 2a 20 50 61 67 65 20 74 68        /* Page th
4d90: 61 74 20 63 6f 6e 74 61 69 6e 73 20 74 68 65 20  at contains the 
4da0: 65 6e 74 72 79 20 2a 2f 0a 20 20 69 6e 74 20 69  entry */.  int i
4db0: 64 78 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  dx;             
4dc0: 20 20 20 20 20 2f 2a 20 49 6e 64 65 78 20 6f 66       /* Index of
4dd0: 20 74 68 65 20 65 6e 74 72 79 20 69 6e 20 70 50   the entry in pP
4de0: 61 67 65 2d 3e 61 43 65 6c 6c 5b 5d 20 2a 2f 0a  age->aCell[] */.
4df0: 20 20 43 65 6c 6c 49 6e 66 6f 20 69 6e 66 6f 3b    CellInfo info;
4e00: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 41              /* A
4e10: 20 70 61 72 73 65 20 6f 66 20 74 68 65 20 63 65   parse of the ce
4e20: 6c 6c 20 77 65 20 61 72 65 20 70 6f 69 6e 74 69  ll we are pointi
4e30: 6e 67 20 61 74 20 2a 2f 0a 20 20 75 38 20 77 72  ng at */.  u8 wr
4e40: 46 6c 61 67 3b 20 20 20 20 20 20 20 20 20 20 20  Flag;           
4e50: 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69 66 20       /* True if 
4e60: 77 72 69 74 61 62 6c 65 20 2a 2f 0a 20 20 75 38  writable */.  u8
4e70: 20 65 53 74 61 74 65 3b 20 20 20 20 20 20 20 20   eState;        
4e80: 20 20 20 20 20 20 20 20 2f 2a 20 4f 6e 65 20 6f          /* One o
4e90: 66 20 74 68 65 20 43 55 52 53 4f 52 5f 58 58 58  f the CURSOR_XXX
4ea0: 20 63 6f 6e 73 74 61 6e 74 73 20 28 73 65 65 20   constants (see 
4eb0: 62 65 6c 6f 77 29 20 2a 2f 0a 20 20 76 6f 69 64  below) */.  void
4ec0: 20 2a 70 4b 65 79 3b 20 20 20 20 20 20 2f 2a 20   *pKey;      /* 
4ed0: 53 61 76 65 64 20 6b 65 79 20 74 68 61 74 20 77  Saved key that w
4ee0: 61 73 20 63 75 72 73 6f 72 27 73 20 6c 61 73 74  as cursor's last
4ef0: 20 6b 6e 6f 77 6e 20 70 6f 73 69 74 69 6f 6e 20   known position 
4f00: 2a 2f 0a 20 20 69 36 34 20 6e 4b 65 79 3b 20 20  */.  i64 nKey;  
4f10: 20 20 20 20 20 20 2f 2a 20 53 69 7a 65 20 6f 66        /* Size of
4f20: 20 70 4b 65 79 2c 20 6f 72 20 6c 61 73 74 20 69   pKey, or last i
4f30: 6e 74 65 67 65 72 20 6b 65 79 20 2a 2f 0a 20 20  nteger key */.  
4f40: 69 6e 74 20 73 6b 69 70 3b 20 20 20 20 20 20 20  int skip;       
4f50: 20 2f 2a 20 28 73 6b 69 70 3c 30 29 20 2d 3e 20   /* (skip<0) -> 
4f60: 50 72 65 76 28 29 20 69 73 20 61 20 6e 6f 2d 6f  Prev() is a no-o
4f70: 70 2e 20 28 73 6b 69 70 3e 30 29 20 2d 3e 20 4e  p. (skip>0) -> N
4f80: 65 78 74 28 29 20 69 73 20 2a 2f 0a 23 69 66 6e  ext() is */.#ifn
4f90: 64 65 66 20 53 51 4c 49 54 45 5f 4f 4d 49 54 5f  def SQLITE_OMIT_
4fa0: 49 4e 43 52 42 4c 4f 42 0a 20 20 75 38 20 69 73  INCRBLOB.  u8 is
4fb0: 49 6e 63 72 62 6c 6f 62 48 61 6e 64 6c 65 3b 20  IncrblobHandle; 
4fc0: 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69 66 20       /* True if 
4fd0: 74 68 69 73 20 63 75 72 73 6f 72 20 69 73 20 61  this cursor is a
4fe0: 6e 20 69 6e 63 72 2e 20 69 6f 20 68 61 6e 64 6c  n incr. io handl
4ff0: 65 20 2a 2f 0a 20 20 50 67 6e 6f 20 2a 61 4f 76  e */.  Pgno *aOv
5000: 65 72 66 6c 6f 77 3b 20 20 20 20 20 20 20 20 20  erflow;         
5010: 20 2f 2a 20 43 61 63 68 65 20 6f 66 20 6f 76 65   /* Cache of ove
5020: 72 66 6c 6f 77 20 70 61 67 65 20 6c 6f 63 61 74  rflow page locat
5030: 69 6f 6e 73 20 2a 2f 0a 23 65 6e 64 69 66 0a 7d  ions */.#endif.}
5040: 3b 0a 0a 2f 2a 0a 2a 2a 20 50 6f 74 65 6e 74 69  ;../*.** Potenti
5050: 61 6c 20 76 61 6c 75 65 73 20 66 6f 72 20 42 74  al values for Bt
5060: 43 75 72 73 6f 72 2e 65 53 74 61 74 65 2e 0a 2a  Cursor.eState..*
5070: 2a 0a 2a 2a 20 43 55 52 53 4f 52 5f 56 41 4c 49  *.** CURSOR_VALI
5080: 44 3a 0a 2a 2a 20 20 20 43 75 72 73 6f 72 20 70  D:.**   Cursor p
5090: 6f 69 6e 74 73 20 74 6f 20 61 20 76 61 6c 69 64  oints to a valid
50a0: 20 65 6e 74 72 79 2e 20 67 65 74 50 61 79 6c 6f   entry. getPaylo
50b0: 61 64 28 29 20 65 74 63 2e 20 6d 61 79 20 62 65  ad() etc. may be
50c0: 20 63 61 6c 6c 65 64 2e 0a 2a 2a 0a 2a 2a 20 43   called..**.** C
50d0: 55 52 53 4f 52 5f 49 4e 56 41 4c 49 44 3a 0a 2a  URSOR_INVALID:.*
50e0: 2a 20 20 20 43 75 72 73 6f 72 20 64 6f 65 73 20  *   Cursor does 
50f0: 6e 6f 74 20 70 6f 69 6e 74 20 74 6f 20 61 20 76  not point to a v
5100: 61 6c 69 64 20 65 6e 74 72 79 2e 20 54 68 69 73  alid entry. This
5110: 20 63 61 6e 20 68 61 70 70 65 6e 20 28 66 6f 72   can happen (for
5120: 20 65 78 61 6d 70 6c 65 29 20 0a 2a 2a 20 20 20   example) .**   
5130: 62 65 63 61 75 73 65 20 74 68 65 20 74 61 62 6c  because the tabl
5140: 65 20 69 73 20 65 6d 70 74 79 20 6f 72 20 62 65  e is empty or be
5150: 63 61 75 73 65 20 42 74 72 65 65 43 75 72 73 6f  cause BtreeCurso
5160: 72 46 69 72 73 74 28 29 20 68 61 73 20 6e 6f 74  rFirst() has not
5170: 20 62 65 65 6e 0a 2a 2a 20 20 20 63 61 6c 6c 65   been.**   calle
5180: 64 2e 0a 2a 2a 0a 2a 2a 20 43 55 52 53 4f 52 5f  d..**.** CURSOR_
5190: 52 45 51 55 49 52 45 53 45 45 4b 3a 0a 2a 2a 20  REQUIRESEEK:.** 
51a0: 20 20 54 68 65 20 74 61 62 6c 65 20 74 68 61 74    The table that
51b0: 20 74 68 69 73 20 63 75 72 73 6f 72 20 77 61 73   this cursor was
51c0: 20 6f 70 65 6e 65 64 20 6f 6e 20 73 74 69 6c 6c   opened on still
51d0: 20 65 78 69 73 74 73 2c 20 62 75 74 20 68 61 73   exists, but has
51e0: 20 62 65 65 6e 20 0a 2a 2a 20 20 20 6d 6f 64 69   been .**   modi
51f0: 66 69 65 64 20 73 69 6e 63 65 20 74 68 65 20 63  fied since the c
5200: 75 72 73 6f 72 20 77 61 73 20 6c 61 73 74 20 75  ursor was last u
5210: 73 65 64 2e 20 54 68 65 20 63 75 72 73 6f 72 20  sed. The cursor 
5220: 70 6f 73 69 74 69 6f 6e 20 69 73 20 73 61 76 65  position is save
5230: 64 0a 2a 2a 20 20 20 69 6e 20 76 61 72 69 61 62  d.**   in variab
5240: 6c 65 73 20 42 74 43 75 72 73 6f 72 2e 70 4b 65  les BtCursor.pKe
5250: 79 20 61 6e 64 20 42 74 43 75 72 73 6f 72 2e 6e  y and BtCursor.n
5260: 4b 65 79 2e 20 57 68 65 6e 20 61 20 63 75 72 73  Key. When a curs
5270: 6f 72 20 69 73 20 69 6e 20 0a 2a 2a 20 20 20 74  or is in .**   t
5280: 68 69 73 20 73 74 61 74 65 2c 20 72 65 73 74 6f  his state, resto
5290: 72 65 4f 72 43 6c 65 61 72 43 75 72 73 6f 72 50  reOrClearCursorP
52a0: 6f 73 69 74 69 6f 6e 28 29 20 63 61 6e 20 62 65  osition() can be
52b0: 20 63 61 6c 6c 65 64 20 74 6f 20 61 74 74 65 6d   called to attem
52c0: 70 74 20 74 6f 0a 2a 2a 20 20 20 73 65 65 6b 20  pt to.**   seek 
52d0: 74 68 65 20 63 75 72 73 6f 72 20 74 6f 20 74 68  the cursor to th
52e0: 65 20 73 61 76 65 64 20 70 6f 73 69 74 69 6f 6e  e saved position
52f0: 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 43 55 52  ..*/.#define CUR
5300: 53 4f 52 5f 49 4e 56 41 4c 49 44 20 20 20 20 20  SOR_INVALID     
5310: 20 20 20 20 20 20 30 0a 23 64 65 66 69 6e 65 20        0.#define 
5320: 43 55 52 53 4f 52 5f 56 41 4c 49 44 20 20 20 20  CURSOR_VALID    
5330: 20 20 20 20 20 20 20 20 20 31 0a 23 64 65 66 69           1.#defi
5340: 6e 65 20 43 55 52 53 4f 52 5f 52 45 51 55 49 52  ne CURSOR_REQUIR
5350: 45 53 45 45 4b 20 20 20 20 20 20 20 32 0a 0a 2f  ESEEK       2../
5360: 2a 0a 2a 2a 20 54 68 65 20 54 52 41 43 45 20 6d  *.** The TRACE m
5370: 61 63 72 6f 20 77 69 6c 6c 20 70 72 69 6e 74 20  acro will print 
5380: 68 69 67 68 2d 6c 65 76 65 6c 20 73 74 61 74 75  high-level statu
5390: 73 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 61 62  s information ab
53a0: 6f 75 74 20 74 68 65 0a 2a 2a 20 62 74 72 65 65  out the.** btree
53b0: 20 6f 70 65 72 61 74 69 6f 6e 20 77 68 65 6e 20   operation when 
53c0: 74 68 65 20 67 6c 6f 62 61 6c 20 76 61 72 69 61  the global varia
53d0: 62 6c 65 20 73 71 6c 69 74 65 33 5f 62 74 72 65  ble sqlite3_btre
53e0: 65 5f 74 72 61 63 65 20 69 73 0a 2a 2a 20 65 6e  e_trace is.** en
53f0: 61 62 6c 65 64 2e 0a 2a 2f 0a 23 69 66 20 53 51  abled..*/.#if SQ
5400: 4c 49 54 45 5f 54 45 53 54 0a 23 20 64 65 66 69  LITE_TEST.# defi
5410: 6e 65 20 54 52 41 43 45 28 58 29 20 20 20 69 66  ne TRACE(X)   if
5420: 28 20 73 71 6c 69 74 65 33 5f 62 74 72 65 65 5f  ( sqlite3_btree_
5430: 74 72 61 63 65 20 29 7b 20 70 72 69 6e 74 66 20  trace ){ printf 
5440: 58 3b 20 66 66 6c 75 73 68 28 73 74 64 6f 75 74  X; fflush(stdout
5450: 29 3b 20 7d 0a 23 65 6c 73 65 0a 23 20 64 65 66  ); }.#else.# def
5460: 69 6e 65 20 54 52 41 43 45 28 58 29 0a 23 65 6e  ine TRACE(X).#en
5470: 64 69 66 0a 0a 2f 2a 0a 2a 2a 20 52 6f 75 74 69  dif../*.** Routi
5480: 6e 65 73 20 74 6f 20 72 65 61 64 20 61 6e 64 20  nes to read and 
5490: 77 72 69 74 65 20 76 61 72 69 61 62 6c 65 2d 6c  write variable-l
54a0: 65 6e 67 74 68 20 69 6e 74 65 67 65 72 73 2e 20  ength integers. 
54b0: 20 54 68 65 73 65 20 75 73 65 64 20 74 6f 0a 2a   These used to.*
54c0: 2a 20 62 65 20 64 65 66 69 6e 65 64 20 6c 6f 63  * be defined loc
54d0: 61 6c 6c 79 2c 20 62 75 74 20 6e 6f 77 20 77 65  ally, but now we
54e0: 20 75 73 65 20 74 68 65 20 76 61 72 69 6e 74 20   use the varint 
54f0: 72 6f 75 74 69 6e 65 73 20 69 6e 20 74 68 65 20  routines in the 
5500: 75 74 69 6c 2e 63 0a 2a 2a 20 66 69 6c 65 2e 0a  util.c.** file..
5510: 2a 2f 0a 23 64 65 66 69 6e 65 20 67 65 74 56 61  */.#define getVa
5520: 72 69 6e 74 20 20 20 20 73 71 6c 69 74 65 33 47  rint    sqlite3G
5530: 65 74 56 61 72 69 6e 74 0a 23 64 65 66 69 6e 65  etVarint.#define
5540: 20 67 65 74 56 61 72 69 6e 74 33 32 28 41 2c 42   getVarint32(A,B
5550: 29 20 20 28 28 2a 42 3d 2a 28 41 29 29 3c 3d 30  )  ((*B=*(A))<=0
5560: 78 37 66 3f 31 3a 73 71 6c 69 74 65 33 47 65 74  x7f?1:sqlite3Get
5570: 56 61 72 69 6e 74 33 32 28 41 2c 42 29 29 0a 23  Varint32(A,B)).#
5580: 64 65 66 69 6e 65 20 70 75 74 56 61 72 69 6e 74  define putVarint
5590: 20 20 20 20 73 71 6c 69 74 65 33 50 75 74 56 61      sqlite3PutVa
55a0: 72 69 6e 74 0a 0a 2f 2a 20 54 68 65 20 64 61 74  rint../* The dat
55b0: 61 62 61 73 65 20 70 61 67 65 20 74 68 65 20 50  abase page the P
55c0: 45 4e 44 49 4e 47 5f 42 59 54 45 20 6f 63 63 75  ENDING_BYTE occu
55d0: 70 69 65 73 2e 20 54 68 69 73 20 70 61 67 65 20  pies. This page 
55e0: 69 73 20 6e 65 76 65 72 20 75 73 65 64 2e 0a 2a  is never used..*
55f0: 2a 20 54 4f 44 4f 3a 20 54 68 69 73 20 6d 61 63  * TODO: This mac
5600: 72 6f 20 69 73 20 76 65 72 79 20 73 69 6d 69 6c  ro is very simil
5610: 61 72 79 20 74 6f 20 50 41 47 45 52 5f 4d 4a 5f  ary to PAGER_MJ_
5620: 50 47 4e 4f 28 29 20 69 6e 20 70 61 67 65 72 2e  PGNO() in pager.
5630: 63 2e 20 54 68 65 79 0a 2a 2a 20 73 68 6f 75 6c  c. They.** shoul
5640: 64 20 70 6f 73 73 69 62 6c 79 20 62 65 20 63 6f  d possibly be co
5650: 6e 73 6f 6c 69 64 61 74 65 64 20 28 70 72 65 73  nsolidated (pres
5660: 75 6d 61 62 6c 79 20 69 6e 20 70 61 67 65 72 2e  umably in pager.
5670: 68 29 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 64 69 73  h)..**.** If dis
5680: 6b 20 49 2f 4f 20 69 73 20 6f 6d 69 74 74 65 64  k I/O is omitted
5690: 20 28 6d 65 61 6e 69 6e 67 20 74 68 61 74 20 74   (meaning that t
56a0: 68 65 20 64 61 74 61 62 61 73 65 20 69 73 20 73  he database is s
56b0: 74 6f 72 65 64 20 70 75 72 65 6c 79 0a 2a 2a 20  tored purely.** 
56c0: 69 6e 20 6d 65 6d 6f 72 79 29 20 74 68 65 6e 20  in memory) then 
56d0: 74 68 65 72 65 20 69 73 20 6e 6f 20 70 65 6e 64  there is no pend
56e0: 69 6e 67 20 62 79 74 65 2e 0a 2a 2f 0a 23 69 66  ing byte..*/.#if
56f0: 64 65 66 20 53 51 4c 49 54 45 5f 4f 4d 49 54 5f  def SQLITE_OMIT_
5700: 44 49 53 4b 49 4f 0a 23 20 64 65 66 69 6e 65 20  DISKIO.# define 
5710: 50 45 4e 44 49 4e 47 5f 42 59 54 45 5f 50 41 47  PENDING_BYTE_PAG
5720: 45 28 70 42 74 29 20 20 30 78 37 66 66 66 66 66  E(pBt)  0x7fffff
5730: 66 66 0a 23 65 6c 73 65 0a 23 20 64 65 66 69 6e  ff.#else.# defin
5740: 65 20 50 45 4e 44 49 4e 47 5f 42 59 54 45 5f 50  e PENDING_BYTE_P
5750: 41 47 45 28 70 42 74 29 20 28 28 50 45 4e 44 49  AGE(pBt) ((PENDI
5760: 4e 47 5f 42 59 54 45 2f 28 70 42 74 29 2d 3e 70  NG_BYTE/(pBt)->p
5770: 61 67 65 53 69 7a 65 29 2b 31 29 0a 23 65 6e 64  ageSize)+1).#end
5780: 69 66 0a 0a 2f 2a 0a 2a 2a 20 41 20 6c 69 6e 6b  if../*.** A link
5790: 65 64 20 6c 69 73 74 20 6f 66 20 74 68 65 20 66  ed list of the f
57a0: 6f 6c 6c 6f 77 69 6e 67 20 73 74 72 75 63 74 75  ollowing structu
57b0: 72 65 73 20 69 73 20 73 74 6f 72 65 64 20 61 74  res is stored at
57c0: 20 42 74 53 68 61 72 65 64 2e 70 4c 6f 63 6b 2e   BtShared.pLock.
57d0: 0a 2a 2a 20 4c 6f 63 6b 73 20 61 72 65 20 61 64  .** Locks are ad
57e0: 64 65 64 20 28 6f 72 20 75 70 67 72 61 64 65 64  ded (or upgraded
57f0: 20 66 72 6f 6d 20 52 45 41 44 5f 4c 4f 43 4b 20   from READ_LOCK 
5800: 74 6f 20 57 52 49 54 45 5f 4c 4f 43 4b 29 20 77  to WRITE_LOCK) w
5810: 68 65 6e 20 61 20 63 75 72 73 6f 72 20 0a 2a 2a  hen a cursor .**
5820: 20 69 73 20 6f 70 65 6e 65 64 20 6f 6e 20 74 68   is opened on th
5830: 65 20 74 61 62 6c 65 20 77 69 74 68 20 72 6f 6f  e table with roo
5840: 74 20 70 61 67 65 20 42 74 53 68 61 72 65 64 2e  t page BtShared.
5850: 69 54 61 62 6c 65 2e 20 4c 6f 63 6b 73 20 61 72  iTable. Locks ar
5860: 65 20 72 65 6d 6f 76 65 64 0a 2a 2a 20 66 72 6f  e removed.** fro
5870: 6d 20 74 68 69 73 20 6c 69 73 74 20 77 68 65 6e  m this list when
5880: 20 61 20 74 72 61 6e 73 61 63 74 69 6f 6e 20 69   a transaction i
5890: 73 20 63 6f 6d 6d 69 74 74 65 64 20 6f 72 20 72  s committed or r
58a0: 6f 6c 6c 65 64 20 62 61 63 6b 2c 20 6f 72 20 77  olled back, or w
58b0: 68 65 6e 0a 2a 2a 20 61 20 62 74 72 65 65 20 68  hen.** a btree h
58c0: 61 6e 64 6c 65 20 69 73 20 63 6c 6f 73 65 64 2e  andle is closed.
58d0: 0a 2a 2f 0a 73 74 72 75 63 74 20 42 74 4c 6f 63  .*/.struct BtLoc
58e0: 6b 20 7b 0a 20 20 42 74 72 65 65 20 2a 70 42 74  k {.  Btree *pBt
58f0: 72 65 65 3b 20 20 20 20 20 20 20 20 2f 2a 20 42  ree;        /* B
5900: 74 72 65 65 20 68 61 6e 64 6c 65 20 68 6f 6c 64  tree handle hold
5910: 69 6e 67 20 74 68 69 73 20 6c 6f 63 6b 20 2a 2f  ing this lock */
5920: 0a 20 20 50 67 6e 6f 20 69 54 61 62 6c 65 3b 20  .  Pgno iTable; 
5930: 20 20 20 20 20 20 20 20 20 2f 2a 20 52 6f 6f 74           /* Root
5940: 20 70 61 67 65 20 6f 66 20 74 61 62 6c 65 20 2a   page of table *
5950: 2f 0a 20 20 75 38 20 65 4c 6f 63 6b 3b 20 20 20  /.  u8 eLock;   
5960: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 52 45 41            /* REA
5970: 44 5f 4c 4f 43 4b 20 6f 72 20 57 52 49 54 45 5f  D_LOCK or WRITE_
5980: 4c 4f 43 4b 20 2a 2f 0a 20 20 42 74 4c 6f 63 6b  LOCK */.  BtLock
5990: 20 2a 70 4e 65 78 74 3b 20 20 20 20 20 20 20 20   *pNext;        
59a0: 2f 2a 20 4e 65 78 74 20 69 6e 20 42 74 53 68 61  /* Next in BtSha
59b0: 72 65 64 2e 70 4c 6f 63 6b 20 6c 69 73 74 20 2a  red.pLock list *
59c0: 2f 0a 7d 3b 0a 0a 2f 2a 20 43 61 6e 64 69 64 61  /.};../* Candida
59d0: 74 65 20 76 61 6c 75 65 73 20 66 6f 72 20 42 74  te values for Bt
59e0: 4c 6f 63 6b 2e 65 4c 6f 63 6b 20 2a 2f 0a 23 64  Lock.eLock */.#d
59f0: 65 66 69 6e 65 20 52 45 41 44 5f 4c 4f 43 4b 20  efine READ_LOCK 
5a00: 20 20 20 20 31 0a 23 64 65 66 69 6e 65 20 57 52      1.#define WR
5a10: 49 54 45 5f 4c 4f 43 4b 20 20 20 20 32 0a 0a 2f  ITE_LOCK    2../
5a20: 2a 0a 2a 2a 20 54 68 65 73 65 20 6d 61 63 72 6f  *.** These macro
5a30: 73 20 64 65 66 69 6e 65 20 74 68 65 20 6c 6f 63  s define the loc
5a40: 61 74 69 6f 6e 20 6f 66 20 74 68 65 20 70 6f 69  ation of the poi
5a50: 6e 74 65 72 2d 6d 61 70 20 65 6e 74 72 79 20 66  nter-map entry f
5a60: 6f 72 20 61 20 0a 2a 2a 20 64 61 74 61 62 61 73  or a .** databas
5a70: 65 20 70 61 67 65 2e 20 54 68 65 20 66 69 72 73  e page. The firs
5a80: 74 20 61 72 67 75 6d 65 6e 74 20 74 6f 20 65 61  t argument to ea
5a90: 63 68 20 69 73 20 74 68 65 20 6e 75 6d 62 65 72  ch is the number
5aa0: 20 6f 66 20 75 73 61 62 6c 65 0a 2a 2a 20 62 79   of usable.** by
5ab0: 74 65 73 20 6f 6e 20 65 61 63 68 20 70 61 67 65  tes on each page
5ac0: 20 6f 66 20 74 68 65 20 64 61 74 61 62 61 73 65   of the database
5ad0: 20 28 6f 66 74 65 6e 20 31 30 32 34 29 2e 20 54   (often 1024). T
5ae0: 68 65 20 73 65 63 6f 6e 64 20 69 73 20 74 68 65  he second is the
5af0: 0a 2a 2a 20 70 61 67 65 20 6e 75 6d 62 65 72 20  .** page number 
5b00: 74 6f 20 6c 6f 6f 6b 20 75 70 20 69 6e 20 74 68  to look up in th
5b10: 65 20 70 6f 69 6e 74 65 72 20 6d 61 70 2e 0a 2a  e pointer map..*
5b20: 2a 0a 2a 2a 20 50 54 52 4d 41 50 5f 50 41 47 45  *.** PTRMAP_PAGE
5b30: 4e 4f 20 72 65 74 75 72 6e 73 20 74 68 65 20 64  NO returns the d
5b40: 61 74 61 62 61 73 65 20 70 61 67 65 20 6e 75 6d  atabase page num
5b50: 62 65 72 20 6f 66 20 74 68 65 20 70 6f 69 6e 74  ber of the point
5b60: 65 72 2d 6d 61 70 0a 2a 2a 20 70 61 67 65 20 74  er-map.** page t
5b70: 68 61 74 20 73 74 6f 72 65 73 20 74 68 65 20 72  hat stores the r
5b80: 65 71 75 69 72 65 64 20 70 6f 69 6e 74 65 72 2e  equired pointer.
5b90: 20 50 54 52 4d 41 50 5f 50 54 52 4f 46 46 53 45   PTRMAP_PTROFFSE
5ba0: 54 20 72 65 74 75 72 6e 73 0a 2a 2a 20 74 68 65  T returns.** the
5bb0: 20 6f 66 66 73 65 74 20 6f 66 20 74 68 65 20 72   offset of the r
5bc0: 65 71 75 65 73 74 65 64 20 6d 61 70 20 65 6e 74  equested map ent
5bd0: 72 79 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 74 68 65  ry..**.** If the
5be0: 20 70 67 6e 6f 20 61 72 67 75 6d 65 6e 74 20 70   pgno argument p
5bf0: 61 73 73 65 64 20 74 6f 20 50 54 52 4d 41 50 5f  assed to PTRMAP_
5c00: 50 41 47 45 4e 4f 20 69 73 20 61 20 70 6f 69 6e  PAGENO is a poin
5c10: 74 65 72 2d 6d 61 70 20 70 61 67 65 2c 0a 2a 2a  ter-map page,.**
5c20: 20 74 68 65 6e 20 70 67 6e 6f 20 69 73 20 72 65   then pgno is re
5c30: 74 75 72 6e 65 64 2e 20 53 6f 20 28 70 67 6e 6f  turned. So (pgno
5c40: 3d 3d 50 54 52 4d 41 50 5f 50 41 47 45 4e 4f 28  ==PTRMAP_PAGENO(
5c50: 70 67 73 7a 2c 20 70 67 6e 6f 29 29 20 63 61 6e  pgsz, pgno)) can
5c60: 20 62 65 0a 2a 2a 20 75 73 65 64 20 74 6f 20 74   be.** used to t
5c70: 65 73 74 20 69 66 20 70 67 6e 6f 20 69 73 20 61  est if pgno is a
5c80: 20 70 6f 69 6e 74 65 72 2d 6d 61 70 20 70 61 67   pointer-map pag
5c90: 65 2e 20 50 54 52 4d 41 50 5f 49 53 50 41 47 45  e. PTRMAP_ISPAGE
5ca0: 20 69 6d 70 6c 65 6d 65 6e 74 73 0a 2a 2a 20 74   implements.** t
5cb0: 68 69 73 20 74 65 73 74 2e 0a 2a 2f 0a 23 64 65  his test..*/.#de
5cc0: 66 69 6e 65 20 50 54 52 4d 41 50 5f 50 41 47 45  fine PTRMAP_PAGE
5cd0: 4e 4f 28 70 42 74 2c 20 70 67 6e 6f 29 20 70 74  NO(pBt, pgno) pt
5ce0: 72 6d 61 70 50 61 67 65 6e 6f 28 70 42 74 2c 20  rmapPageno(pBt, 
5cf0: 70 67 6e 6f 29 0a 23 64 65 66 69 6e 65 20 50 54  pgno).#define PT
5d00: 52 4d 41 50 5f 50 54 52 4f 46 46 53 45 54 28 70  RMAP_PTROFFSET(p
5d10: 42 74 2c 20 70 67 6e 6f 29 20 28 35 2a 28 70 67  Bt, pgno) (5*(pg
5d20: 6e 6f 2d 70 74 72 6d 61 70 50 61 67 65 6e 6f 28  no-ptrmapPageno(
5d30: 70 42 74 2c 20 70 67 6e 6f 29 2d 31 29 29 0a 23  pBt, pgno)-1)).#
5d40: 64 65 66 69 6e 65 20 50 54 52 4d 41 50 5f 49 53  define PTRMAP_IS
5d50: 50 41 47 45 28 70 42 74 2c 20 70 67 6e 6f 29 20  PAGE(pBt, pgno) 
5d60: 28 50 54 52 4d 41 50 5f 50 41 47 45 4e 4f 28 28  (PTRMAP_PAGENO((
5d70: 70 42 74 29 2c 28 70 67 6e 6f 29 29 3d 3d 28 70  pBt),(pgno))==(p
5d80: 67 6e 6f 29 29 0a 0a 2f 2a 0a 2a 2a 20 54 68 65  gno))../*.** The
5d90: 20 70 6f 69 6e 74 65 72 20 6d 61 70 20 69 73 20   pointer map is 
5da0: 61 20 6c 6f 6f 6b 75 70 20 74 61 62 6c 65 20 74  a lookup table t
5db0: 68 61 74 20 69 64 65 6e 74 69 66 69 65 73 20 74  hat identifies t
5dc0: 68 65 20 70 61 72 65 6e 74 20 70 61 67 65 20 66  he parent page f
5dd0: 6f 72 0a 2a 2a 20 65 61 63 68 20 63 68 69 6c 64  or.** each child
5de0: 20 70 61 67 65 20 69 6e 20 74 68 65 20 64 61 74   page in the dat
5df0: 61 62 61 73 65 20 66 69 6c 65 2e 20 20 54 68 65  abase file.  The
5e00: 20 70 61 72 65 6e 74 20 70 61 67 65 20 69 73 20   parent page is 
5e10: 74 68 65 20 70 61 67 65 20 74 68 61 74 0a 2a 2a  the page that.**
5e20: 20 63 6f 6e 74 61 69 6e 73 20 61 20 70 6f 69 6e   contains a poin
5e30: 74 65 72 20 74 6f 20 74 68 65 20 63 68 69 6c 64  ter to the child
5e40: 2e 20 20 45 76 65 72 79 20 70 61 67 65 20 69 6e  .  Every page in
5e50: 20 74 68 65 20 64 61 74 61 62 61 73 65 20 63 6f   the database co
5e60: 6e 74 61 69 6e 73 0a 2a 2a 20 30 20 6f 72 20 31  ntains.** 0 or 1
5e70: 20 70 61 72 65 6e 74 20 70 61 67 65 73 2e 20 20   parent pages.  
5e80: 28 49 6e 20 74 68 69 73 20 63 6f 6e 74 65 78 74  (In this context
5e90: 20 27 64 61 74 61 62 61 73 65 20 70 61 67 65 27   'database page'
5ea0: 20 72 65 66 65 72 73 0a 2a 2a 20 74 6f 20 61 6e   refers.** to an
5eb0: 79 20 70 61 67 65 20 74 68 61 74 20 69 73 20 6e  y page that is n
5ec0: 6f 74 20 70 61 72 74 20 6f 66 20 74 68 65 20 70  ot part of the p
5ed0: 6f 69 6e 74 65 72 20 6d 61 70 20 69 74 73 65 6c  ointer map itsel
5ee0: 66 2e 29 20 20 45 61 63 68 20 70 6f 69 6e 74 65  f.)  Each pointe
5ef0: 72 20 6d 61 70 0a 2a 2a 20 65 6e 74 72 79 20 63  r map.** entry c
5f00: 6f 6e 73 69 73 74 73 20 6f 66 20 61 20 73 69 6e  onsists of a sin
5f10: 67 6c 65 20 62 79 74 65 20 27 74 79 70 65 27 20  gle byte 'type' 
5f20: 61 6e 64 20 61 20 34 20 62 79 74 65 20 70 61 72  and a 4 byte par
5f30: 65 6e 74 20 70 61 67 65 20 6e 75 6d 62 65 72 2e  ent page number.
5f40: 0a 2a 2a 20 54 68 65 20 50 54 52 4d 41 50 5f 58  .** The PTRMAP_X
5f50: 58 58 20 69 64 65 6e 74 69 66 69 65 72 73 20 62  XX identifiers b
5f60: 65 6c 6f 77 20 61 72 65 20 74 68 65 20 76 61 6c  elow are the val
5f70: 69 64 20 74 79 70 65 73 2e 0a 2a 2a 0a 2a 2a 20  id types..**.** 
5f80: 54 68 65 20 70 75 72 70 6f 73 65 20 6f 66 20 74  The purpose of t
5f90: 68 65 20 70 6f 69 6e 74 65 72 20 6d 61 70 20 69  he pointer map i
5fa0: 73 20 74 6f 20 66 61 63 69 6c 69 74 79 20 6d 6f  s to facility mo
5fb0: 76 69 6e 67 20 70 61 67 65 73 20 66 72 6f 6d 20  ving pages from 
5fc0: 6f 6e 65 0a 2a 2a 20 70 6f 73 69 74 69 6f 6e 20  one.** position 
5fd0: 69 6e 20 74 68 65 20 66 69 6c 65 20 74 6f 20 61  in the file to a
5fe0: 6e 6f 74 68 65 72 20 61 73 20 70 61 72 74 20 6f  nother as part o
5ff0: 66 20 61 75 74 6f 76 61 63 75 75 6d 2e 20 20 57  f autovacuum.  W
6000: 68 65 6e 20 61 20 70 61 67 65 0a 2a 2a 20 69 73  hen a page.** is
6010: 20 6d 6f 76 65 64 2c 20 74 68 65 20 70 6f 69 6e   moved, the poin
6020: 74 65 72 20 69 6e 20 69 74 73 20 70 61 72 65 6e  ter in its paren
6030: 74 20 6d 75 73 74 20 62 65 20 75 70 64 61 74 65  t must be update
6040: 64 20 74 6f 20 70 6f 69 6e 74 20 74 6f 20 74 68  d to point to th
6050: 65 0a 2a 2a 20 6e 65 77 20 6c 6f 63 61 74 69 6f  e.** new locatio
6060: 6e 2e 20 20 54 68 65 20 70 6f 69 6e 74 65 72 20  n.  The pointer 
6070: 6d 61 70 20 69 73 20 75 73 65 64 20 74 6f 20 6c  map is used to l
6080: 6f 63 61 74 65 20 74 68 65 20 70 61 72 65 6e 74  ocate the parent
6090: 20 70 61 67 65 20 71 75 69 63 6b 6c 79 2e 0a 2a   page quickly..*
60a0: 2a 0a 2a 2a 20 50 54 52 4d 41 50 5f 52 4f 4f 54  *.** PTRMAP_ROOT
60b0: 50 41 47 45 3a 20 54 68 65 20 64 61 74 61 62 61  PAGE: The databa
60c0: 73 65 20 70 61 67 65 20 69 73 20 61 20 72 6f 6f  se page is a roo
60d0: 74 2d 70 61 67 65 2e 20 54 68 65 20 70 61 67 65  t-page. The page
60e0: 2d 6e 75 6d 62 65 72 20 69 73 20 6e 6f 74 0a 2a  -number is not.*
60f0: 2a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  *               
6100: 20 20 20 75 73 65 64 20 69 6e 20 74 68 69 73 20     used in this 
6110: 63 61 73 65 2e 0a 2a 2a 0a 2a 2a 20 50 54 52 4d  case..**.** PTRM
6120: 41 50 5f 46 52 45 45 50 41 47 45 3a 20 54 68 65  AP_FREEPAGE: The
6130: 20 64 61 74 61 62 61 73 65 20 70 61 67 65 20 69   database page i
6140: 73 20 61 6e 20 75 6e 75 73 65 64 20 28 66 72 65  s an unused (fre
6150: 65 29 20 70 61 67 65 2e 20 54 68 65 20 70 61 67  e) page. The pag
6160: 65 2d 6e 75 6d 62 65 72 20 0a 2a 2a 20 20 20 20  e-number .**    
6170: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 69 73                is
6180: 20 6e 6f 74 20 75 73 65 64 20 69 6e 20 74 68 69   not used in thi
6190: 73 20 63 61 73 65 2e 0a 2a 2a 0a 2a 2a 20 50 54  s case..**.** PT
61a0: 52 4d 41 50 5f 4f 56 45 52 46 4c 4f 57 31 3a 20  RMAP_OVERFLOW1: 
61b0: 54 68 65 20 64 61 74 61 62 61 73 65 20 70 61 67  The database pag
61c0: 65 20 69 73 20 74 68 65 20 66 69 72 73 74 20 70  e is the first p
61d0: 61 67 65 20 69 6e 20 61 20 6c 69 73 74 20 6f 66  age in a list of
61e0: 20 0a 2a 2a 20 20 20 20 20 20 20 20 20 20 20 20   .**            
61f0: 20 20 20 20 20 20 20 6f 76 65 72 66 6c 6f 77 20         overflow 
6200: 70 61 67 65 73 2e 20 54 68 65 20 70 61 67 65 20  pages. The page 
6210: 6e 75 6d 62 65 72 20 69 64 65 6e 74 69 66 69 65  number identifie
6220: 73 20 74 68 65 20 70 61 67 65 20 74 68 61 74 0a  s the page that.
6230: 2a 2a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  **              
6240: 20 20 20 20 20 63 6f 6e 74 61 69 6e 73 20 74 68       contains th
6250: 65 20 63 65 6c 6c 20 77 69 74 68 20 61 20 70 6f  e cell with a po
6260: 69 6e 74 65 72 20 74 6f 20 74 68 69 73 20 6f 76  inter to this ov
6270: 65 72 66 6c 6f 77 20 70 61 67 65 2e 0a 2a 2a 0a  erflow page..**.
6280: 2a 2a 20 50 54 52 4d 41 50 5f 4f 56 45 52 46 4c  ** PTRMAP_OVERFL
6290: 4f 57 32 3a 20 54 68 65 20 64 61 74 61 62 61 73  OW2: The databas
62a0: 65 20 70 61 67 65 20 69 73 20 74 68 65 20 73 65  e page is the se
62b0: 63 6f 6e 64 20 6f 72 20 6c 61 74 65 72 20 70 61  cond or later pa
62c0: 67 65 20 69 6e 20 61 20 6c 69 73 74 20 6f 66 0a  ge in a list of.
62d0: 2a 2a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  **              
62e0: 20 20 20 20 20 6f 76 65 72 66 6c 6f 77 20 70 61       overflow pa
62f0: 67 65 73 2e 20 54 68 65 20 70 61 67 65 2d 6e 75  ges. The page-nu
6300: 6d 62 65 72 20 69 64 65 6e 74 69 66 69 65 73 20  mber identifies 
6310: 74 68 65 20 70 72 65 76 69 6f 75 73 0a 2a 2a 20  the previous.** 
6320: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
6330: 20 20 70 61 67 65 20 69 6e 20 74 68 65 20 6f 76    page in the ov
6340: 65 72 66 6c 6f 77 20 70 61 67 65 20 6c 69 73 74  erflow page list
6350: 2e 0a 2a 2a 0a 2a 2a 20 50 54 52 4d 41 50 5f 42  ..**.** PTRMAP_B
6360: 54 52 45 45 3a 20 54 68 65 20 64 61 74 61 62 61  TREE: The databa
6370: 73 65 20 70 61 67 65 20 69 73 20 61 20 6e 6f 6e  se page is a non
6380: 2d 72 6f 6f 74 20 62 74 72 65 65 20 70 61 67 65  -root btree page
6390: 2e 20 54 68 65 20 70 61 67 65 20 6e 75 6d 62 65  . The page numbe
63a0: 72 0a 2a 2a 20 20 20 20 20 20 20 20 20 20 20 20  r.**            
63b0: 20 20 20 69 64 65 6e 74 69 66 69 65 73 20 74 68     identifies th
63c0: 65 20 70 61 72 65 6e 74 20 70 61 67 65 20 69 6e  e parent page in
63d0: 20 74 68 65 20 62 74 72 65 65 2e 0a 2a 2f 0a 23   the btree..*/.#
63e0: 64 65 66 69 6e 65 20 50 54 52 4d 41 50 5f 52 4f  define PTRMAP_RO
63f0: 4f 54 50 41 47 45 20 31 0a 23 64 65 66 69 6e 65  OTPAGE 1.#define
6400: 20 50 54 52 4d 41 50 5f 46 52 45 45 50 41 47 45   PTRMAP_FREEPAGE
6410: 20 32 0a 23 64 65 66 69 6e 65 20 50 54 52 4d 41   2.#define PTRMA
6420: 50 5f 4f 56 45 52 46 4c 4f 57 31 20 33 0a 23 64  P_OVERFLOW1 3.#d
6430: 65 66 69 6e 65 20 50 54 52 4d 41 50 5f 4f 56 45  efine PTRMAP_OVE
6440: 52 46 4c 4f 57 32 20 34 0a 23 64 65 66 69 6e 65  RFLOW2 4.#define
6450: 20 50 54 52 4d 41 50 5f 42 54 52 45 45 20 35 0a   PTRMAP_BTREE 5.
6460: 0a 2f 2a 20 41 20 62 75 6e 63 68 20 6f 66 20 61  ./* A bunch of a
6470: 73 73 65 72 74 28 29 20 73 74 61 74 65 6d 65 6e  ssert() statemen
6480: 74 73 20 74 6f 20 63 68 65 63 6b 20 74 68 65 20  ts to check the 
6490: 74 72 61 6e 73 61 63 74 69 6f 6e 20 73 74 61 74  transaction stat
64a0: 65 20 76 61 72 69 61 62 6c 65 73 0a 2a 2a 20 6f  e variables.** o
64b0: 66 20 68 61 6e 64 6c 65 20 70 20 28 74 79 70 65  f handle p (type
64c0: 20 42 74 72 65 65 2a 29 20 61 72 65 20 69 6e 74   Btree*) are int
64d0: 65 72 6e 61 6c 6c 79 20 63 6f 6e 73 69 73 74 65  ernally consiste
64e0: 6e 74 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 62  nt..*/.#define b
64f0: 74 72 65 65 49 6e 74 65 67 72 69 74 79 28 70 29  treeIntegrity(p)
6500: 20 5c 0a 20 20 61 73 73 65 72 74 28 20 70 2d 3e   \.  assert( p->
6510: 70 42 74 2d 3e 69 6e 54 72 61 6e 73 61 63 74 69  pBt->inTransacti
6520: 6f 6e 21 3d 54 52 41 4e 53 5f 4e 4f 4e 45 20 7c  on!=TRANS_NONE |
6530: 7c 20 70 2d 3e 70 42 74 2d 3e 6e 54 72 61 6e 73  | p->pBt->nTrans
6540: 61 63 74 69 6f 6e 3d 3d 30 20 29 3b 20 5c 0a 20  action==0 ); \. 
6550: 20 61 73 73 65 72 74 28 20 70 2d 3e 70 42 74 2d   assert( p->pBt-
6560: 3e 69 6e 54 72 61 6e 73 61 63 74 69 6f 6e 3e 3d  >inTransaction>=
6570: 70 2d 3e 69 6e 54 72 61 6e 73 20 29 3b 20 0a 0a  p->inTrans ); ..
6580: 0a 2f 2a 0a 2a 2a 20 54 68 65 20 49 53 41 55 54  ./*.** The ISAUT
6590: 4f 56 41 43 55 55 4d 20 6d 61 63 72 6f 20 69 73  OVACUUM macro is
65a0: 20 75 73 65 64 20 77 69 74 68 69 6e 20 62 61 6c   used within bal
65b0: 61 6e 63 65 5f 6e 6f 6e 72 6f 6f 74 28 29 20 74  ance_nonroot() t
65c0: 6f 20 64 65 74 65 72 6d 69 6e 65 0a 2a 2a 20 69  o determine.** i
65d0: 66 20 74 68 65 20 64 61 74 61 62 61 73 65 20 73  f the database s
65e0: 75 70 70 6f 72 74 73 20 61 75 74 6f 2d 76 61 63  upports auto-vac
65f0: 75 75 6d 20 6f 72 20 6e 6f 74 2e 20 42 65 63 61  uum or not. Beca
6600: 75 73 65 20 69 74 20 69 73 20 75 73 65 64 0a 2a  use it is used.*
6610: 2a 20 77 69 74 68 69 6e 20 61 6e 20 65 78 70 72  * within an expr
6620: 65 73 73 69 6f 6e 20 74 68 61 74 20 69 73 20 61  ession that is a
6630: 6e 20 61 72 67 75 6d 65 6e 74 20 74 6f 20 61 6e  n argument to an
6640: 6f 74 68 65 72 20 6d 61 63 72 6f 20 0a 2a 2a 20  other macro .** 
6650: 28 73 71 6c 69 74 65 4d 61 6c 6c 6f 63 52 61 77  (sqliteMallocRaw
6660: 29 2c 20 69 74 20 69 73 20 6e 6f 74 20 70 6f 73  ), it is not pos
6670: 73 69 62 6c 65 20 74 6f 20 75 73 65 20 63 6f 6e  sible to use con
6680: 64 69 74 69 6f 6e 61 6c 20 63 6f 6d 70 69 6c 61  ditional compila
6690: 74 69 6f 6e 2e 0a 2a 2a 20 53 6f 2c 20 74 68 69  tion..** So, thi
66a0: 73 20 6d 61 63 72 6f 20 69 73 20 64 65 66 69 6e  s macro is defin
66b0: 65 64 20 69 6e 73 74 65 61 64 2e 0a 2a 2f 0a 23  ed instead..*/.#
66c0: 69 66 6e 64 65 66 20 53 51 4c 49 54 45 5f 4f 4d  ifndef SQLITE_OM
66d0: 49 54 5f 41 55 54 4f 56 41 43 55 55 4d 0a 23 64  IT_AUTOVACUUM.#d
66e0: 65 66 69 6e 65 20 49 53 41 55 54 4f 56 41 43 55  efine ISAUTOVACU
66f0: 55 4d 20 28 70 42 74 2d 3e 61 75 74 6f 56 61 63  UM (pBt->autoVac
6700: 75 75 6d 29 0a 23 65 6c 73 65 0a 23 64 65 66 69  uum).#else.#defi
6710: 6e 65 20 49 53 41 55 54 4f 56 41 43 55 55 4d 20  ne ISAUTOVACUUM 
6720: 30 0a 23 65 6e 64 69 66 0a 0a 0a 2f 2a 0a 2a 2a  0.#endif.../*.**
6730: 20 54 68 69 73 20 73 74 72 75 63 74 75 72 65 20   This structure 
6740: 69 73 20 70 61 73 73 65 64 20 61 72 6f 75 6e 64  is passed around
6750: 20 74 68 72 6f 75 67 68 20 61 6c 6c 20 74 68 65   through all the
6760: 20 73 61 6e 69 74 79 20 63 68 65 63 6b 69 6e 67   sanity checking
6770: 20 72 6f 75 74 69 6e 65 73 0a 2a 2a 20 69 6e 20   routines.** in 
6780: 6f 72 64 65 72 20 74 6f 20 6b 65 65 70 20 74 72  order to keep tr
6790: 61 63 6b 20 6f 66 20 73 6f 6d 65 20 67 6c 6f 62  ack of some glob
67a0: 61 6c 20 73 74 61 74 65 20 69 6e 66 6f 72 6d 61  al state informa
67b0: 74 69 6f 6e 2e 0a 2a 2f 0a 74 79 70 65 64 65 66  tion..*/.typedef
67c0: 20 73 74 72 75 63 74 20 49 6e 74 65 67 72 69 74   struct Integrit
67d0: 79 43 6b 20 49 6e 74 65 67 72 69 74 79 43 6b 3b  yCk IntegrityCk;
67e0: 0a 73 74 72 75 63 74 20 49 6e 74 65 67 72 69 74  .struct Integrit
67f0: 79 43 6b 20 7b 0a 20 20 42 74 53 68 61 72 65 64  yCk {.  BtShared
6800: 20 2a 70 42 74 3b 20 20 20 20 2f 2a 20 54 68 65   *pBt;    /* The
6810: 20 74 72 65 65 20 62 65 69 6e 67 20 63 68 65 63   tree being chec
6820: 6b 65 64 20 6f 75 74 20 2a 2f 0a 20 20 50 61 67  ked out */.  Pag
6830: 65 72 20 2a 70 50 61 67 65 72 3b 20 20 20 20 2f  er *pPager;    /
6840: 2a 20 54 68 65 20 61 73 73 6f 63 69 61 74 65 64  * The associated
6850: 20 70 61 67 65 72 2e 20 20 41 6c 73 6f 20 61 63   pager.  Also ac
6860: 63 65 73 73 69 62 6c 65 20 62 79 20 70 42 74 2d  cessible by pBt-
6870: 3e 70 50 61 67 65 72 20 2a 2f 0a 20 20 69 6e 74  >pPager */.  int
6880: 20 6e 50 61 67 65 3b 20 20 20 20 20 20 20 20 2f   nPage;        /
6890: 2a 20 4e 75 6d 62 65 72 20 6f 66 20 70 61 67 65  * Number of page
68a0: 73 20 69 6e 20 74 68 65 20 64 61 74 61 62 61 73  s in the databas
68b0: 65 20 2a 2f 0a 20 20 69 6e 74 20 2a 61 6e 52 65  e */.  int *anRe
68c0: 66 3b 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62  f;       /* Numb
68d0: 65 72 20 6f 66 20 74 69 6d 65 73 20 65 61 63 68  er of times each
68e0: 20 70 61 67 65 20 69 73 20 72 65 66 65 72 65 6e   page is referen
68f0: 63 65 64 20 2a 2f 0a 20 20 69 6e 74 20 6d 78 45  ced */.  int mxE
6900: 72 72 3b 20 20 20 20 20 20 20 20 2f 2a 20 53 74  rr;        /* St
6910: 6f 70 20 61 63 63 75 6d 75 6c 61 74 69 6e 67 20  op accumulating 
6920: 65 72 72 6f 72 73 20 77 68 65 6e 20 74 68 69 73  errors when this
6930: 20 72 65 61 63 68 65 73 20 7a 65 72 6f 20 2a 2f   reaches zero */
6940: 0a 20 20 63 68 61 72 20 2a 7a 45 72 72 4d 73 67  .  char *zErrMsg
6950: 3b 20 20 20 20 2f 2a 20 41 6e 20 65 72 72 6f 72  ;    /* An error
6960: 20 6d 65 73 73 61 67 65 2e 20 20 4e 55 4c 4c 20   message.  NULL 
6970: 69 66 20 6e 6f 20 65 72 72 6f 72 73 20 73 65 65  if no errors see
6980: 6e 2e 20 2a 2f 0a 20 20 69 6e 74 20 6e 45 72 72  n. */.  int nErr
6990: 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d  ;         /* Num
69a0: 62 65 72 20 6f 66 20 6d 65 73 73 61 67 65 73 20  ber of messages 
69b0: 77 72 69 74 74 65 6e 20 74 6f 20 7a 45 72 72 4d  written to zErrM
69c0: 73 67 20 73 6f 20 66 61 72 20 2a 2f 0a 7d 3b 0a  sg so far */.};.
69d0: 0a 2f 2a 0a 2a 2a 20 52 65 61 64 20 6f 72 20 77  ./*.** Read or w
69e0: 72 69 74 65 20 61 20 74 77 6f 2d 20 61 6e 64 20  rite a two- and 
69f0: 66 6f 75 72 2d 62 79 74 65 20 62 69 67 2d 65 6e  four-byte big-en
6a00: 64 69 61 6e 20 69 6e 74 65 67 65 72 20 76 61 6c  dian integer val
6a10: 75 65 73 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20  ues..*/.#define 
6a20: 67 65 74 32 62 79 74 65 28 78 29 20 20 20 28 28  get2byte(x)   ((
6a30: 78 29 5b 30 5d 3c 3c 38 20 7c 20 28 78 29 5b 31  x)[0]<<8 | (x)[1
6a40: 5d 29 0a 23 64 65 66 69 6e 65 20 70 75 74 32 62  ]).#define put2b
6a50: 79 74 65 28 70 2c 76 29 20 28 28 70 29 5b 30 5d  yte(p,v) ((p)[0]
6a60: 20 3d 20 28 76 29 3e 3e 38 2c 20 28 70 29 5b 31   = (v)>>8, (p)[1
6a70: 5d 20 3d 20 28 76 29 29 0a 23 64 65 66 69 6e 65  ] = (v)).#define
6a80: 20 67 65 74 34 62 79 74 65 20 73 71 6c 69 74 65   get4byte sqlite
6a90: 33 47 65 74 34 62 79 74 65 0a 23 64 65 66 69 6e  3Get4byte.#defin
6aa0: 65 20 70 75 74 34 62 79 74 65 20 73 71 6c 69 74  e put4byte sqlit
6ab0: 65 33 50 75 74 34 62 79 74 65 0a 0a 2f 2a 0a 2a  e3Put4byte../*.*
6ac0: 2a 20 49 6e 74 65 72 6e 61 6c 20 72 6f 75 74 69  * Internal routi
6ad0: 6e 65 73 20 74 68 61 74 20 73 68 6f 75 6c 64 20  nes that should 
6ae0: 62 65 20 61 63 63 65 73 73 65 64 20 62 79 20 74  be accessed by t
6af0: 68 65 20 62 74 72 65 65 20 6c 61 79 65 72 20 6f  he btree layer o
6b00: 6e 6c 79 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c 69  nly..*/.int sqli
6b10: 74 65 33 42 74 72 65 65 47 65 74 50 61 67 65 28  te3BtreeGetPage(
6b20: 42 74 53 68 61 72 65 64 2a 2c 20 50 67 6e 6f 2c  BtShared*, Pgno,
6b30: 20 4d 65 6d 50 61 67 65 2a 2a 2c 20 69 6e 74 29   MemPage**, int)
6b40: 3b 0a 69 6e 74 20 73 71 6c 69 74 65 33 42 74 72  ;.int sqlite3Btr
6b50: 65 65 49 6e 69 74 50 61 67 65 28 4d 65 6d 50 61  eeInitPage(MemPa
6b60: 67 65 20 2a 70 50 61 67 65 2c 20 4d 65 6d 50 61  ge *pPage, MemPa
6b70: 67 65 20 2a 70 50 61 72 65 6e 74 29 3b 0a 76 6f  ge *pParent);.vo
6b80: 69 64 20 73 71 6c 69 74 65 33 42 74 72 65 65 50  id sqlite3BtreeP
6b90: 61 72 73 65 43 65 6c 6c 50 74 72 28 4d 65 6d 50  arseCellPtr(MemP
6ba0: 61 67 65 2a 2c 20 75 38 2a 2c 20 43 65 6c 6c 49  age*, u8*, CellI
6bb0: 6e 66 6f 2a 29 3b 0a 76 6f 69 64 20 73 71 6c 69  nfo*);.void sqli
6bc0: 74 65 33 42 74 72 65 65 50 61 72 73 65 43 65 6c  te3BtreeParseCel
6bd0: 6c 28 4d 65 6d 50 61 67 65 2a 2c 20 69 6e 74 2c  l(MemPage*, int,
6be0: 20 43 65 6c 6c 49 6e 66 6f 2a 29 3b 0a 75 38 20   CellInfo*);.u8 
6bf0: 2a 73 71 6c 69 74 65 33 42 74 72 65 65 46 69 6e  *sqlite3BtreeFin
6c00: 64 43 65 6c 6c 28 4d 65 6d 50 61 67 65 20 2a 70  dCell(MemPage *p
6c10: 50 61 67 65 2c 20 69 6e 74 20 69 43 65 6c 6c 29  Page, int iCell)
6c20: 3b 0a 69 6e 74 20 73 71 6c 69 74 65 33 42 74 72  ;.int sqlite3Btr
6c30: 65 65 52 65 73 74 6f 72 65 4f 72 43 6c 65 61 72  eeRestoreOrClear
6c40: 43 75 72 73 6f 72 50 6f 73 69 74 69 6f 6e 28 42  CursorPosition(B
6c50: 74 43 75 72 73 6f 72 20 2a 70 43 75 72 29 3b 0a  tCursor *pCur);.
6c60: 76 6f 69 64 20 73 71 6c 69 74 65 33 42 74 72 65  void sqlite3Btre
6c70: 65 47 65 74 54 65 6d 70 43 75 72 73 6f 72 28 42  eGetTempCursor(B
6c80: 74 43 75 72 73 6f 72 20 2a 70 43 75 72 2c 20 42  tCursor *pCur, B
6c90: 74 43 75 72 73 6f 72 20 2a 70 54 65 6d 70 43 75  tCursor *pTempCu
6ca0: 72 29 3b 0a 76 6f 69 64 20 73 71 6c 69 74 65 33  r);.void sqlite3
6cb0: 42 74 72 65 65 52 65 6c 65 61 73 65 54 65 6d 70  BtreeReleaseTemp
6cc0: 43 75 72 73 6f 72 28 42 74 43 75 72 73 6f 72 20  Cursor(BtCursor 
6cd0: 2a 70 43 75 72 29 3b 0a 69 6e 74 20 73 71 6c 69  *pCur);.int sqli
6ce0: 74 65 33 42 74 72 65 65 49 73 52 6f 6f 74 50 61  te3BtreeIsRootPa
6cf0: 67 65 28 4d 65 6d 50 61 67 65 20 2a 70 50 61 67  ge(MemPage *pPag
6d00: 65 29 3b 0a 76 6f 69 64 20 73 71 6c 69 74 65 33  e);.void sqlite3
6d10: 42 74 72 65 65 4d 6f 76 65 54 6f 50 61 72 65 6e  BtreeMoveToParen
6d20: 74 28 42 74 43 75 72 73 6f 72 20 2a 70 43 75 72  t(BtCursor *pCur
6d30: 29 3b 0a                                         );.