SQLite
Hex Artifact Content
Not logged in

Artifact cce1c3360cd5549ffa79f981951dfae93118ad79:


0000: 2f 2a 0a 2a 2a 20 32 30 30 34 20 41 70 72 69 6c  /*.** 2004 April
0010: 20 36 0a 2a 2a 0a 2a 2a 20 54 68 65 20 61 75 74   6.**.** The aut
0020: 68 6f 72 20 64 69 73 63 6c 61 69 6d 73 20 63 6f  hor disclaims co
0030: 70 79 72 69 67 68 74 20 74 6f 20 74 68 69 73 20  pyright to this 
0040: 73 6f 75 72 63 65 20 63 6f 64 65 2e 20 20 49 6e  source code.  In
0050: 20 70 6c 61 63 65 20 6f 66 0a 2a 2a 20 61 20 6c   place of.** a l
0060: 65 67 61 6c 20 6e 6f 74 69 63 65 2c 20 68 65 72  egal notice, her
0070: 65 20 69 73 20 61 20 62 6c 65 73 73 69 6e 67 3a  e is a blessing:
0080: 0a 2a 2a 0a 2a 2a 20 20 20 20 4d 61 79 20 79 6f  .**.**    May yo
0090: 75 20 64 6f 20 67 6f 6f 64 20 61 6e 64 20 6e 6f  u do good and no
00a0: 74 20 65 76 69 6c 2e 0a 2a 2a 20 20 20 20 4d 61  t evil..**    Ma
00b0: 79 20 79 6f 75 20 66 69 6e 64 20 66 6f 72 67 69  y you find forgi
00c0: 76 65 6e 65 73 73 20 66 6f 72 20 79 6f 75 72 73  veness for yours
00d0: 65 6c 66 20 61 6e 64 20 66 6f 72 67 69 76 65 20  elf and forgive 
00e0: 6f 74 68 65 72 73 2e 0a 2a 2a 20 20 20 20 4d 61  others..**    Ma
00f0: 79 20 79 6f 75 20 73 68 61 72 65 20 66 72 65 65  y you share free
0100: 6c 79 2c 20 6e 65 76 65 72 20 74 61 6b 69 6e 67  ly, never taking
0110: 20 6d 6f 72 65 20 74 68 61 6e 20 79 6f 75 20 67   more than you g
0120: 69 76 65 2e 0a 2a 2a 0a 2a 2a 2a 2a 2a 2a 2a 2a  ive..**.********
0130: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0140: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0150: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0160: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0170: 2a 0a 2a 2a 20 24 49 64 3a 20 62 74 72 65 65 49  *.** $Id: btreeI
0180: 6e 74 2e 68 2c 76 20 31 2e 35 32 20 32 30 30 39  nt.h,v 1.52 2009
0190: 2f 30 37 2f 31 35 20 31 37 3a 32 35 3a 34 36 20  /07/15 17:25:46 
01a0: 64 72 68 20 45 78 70 20 24 0a 2a 2a 0a 2a 2a 20  drh Exp $.**.** 
01b0: 54 68 69 73 20 66 69 6c 65 20 69 6d 70 6c 65 6d  This file implem
01c0: 65 6e 74 73 20 61 20 65 78 74 65 72 6e 61 6c 20  ents a external 
01d0: 28 64 69 73 6b 2d 62 61 73 65 64 29 20 64 61 74  (disk-based) dat
01e0: 61 62 61 73 65 20 75 73 69 6e 67 20 42 54 72 65  abase using BTre
01f0: 65 73 2e 0a 2a 2a 20 46 6f 72 20 61 20 64 65 74  es..** For a det
0200: 61 69 6c 65 64 20 64 69 73 63 75 73 73 69 6f 6e  ailed discussion
0210: 20 6f 66 20 42 54 72 65 65 73 2c 20 72 65 66 65   of BTrees, refe
0220: 72 20 74 6f 0a 2a 2a 0a 2a 2a 20 20 20 20 20 44  r to.**.**     D
0230: 6f 6e 61 6c 64 20 45 2e 20 4b 6e 75 74 68 2c 20  onald E. Knuth, 
0240: 54 48 45 20 41 52 54 20 4f 46 20 43 4f 4d 50 55  THE ART OF COMPU
0250: 54 45 52 20 50 52 4f 47 52 41 4d 4d 49 4e 47 2c  TER PROGRAMMING,
0260: 20 56 6f 6c 75 6d 65 20 33 3a 0a 2a 2a 20 20 20   Volume 3:.**   
0270: 20 20 22 53 6f 72 74 69 6e 67 20 41 6e 64 20 53    "Sorting And S
0280: 65 61 72 63 68 69 6e 67 22 2c 20 70 61 67 65 73  earching", pages
0290: 20 34 37 33 2d 34 38 30 2e 20 41 64 64 69 73 6f   473-480. Addiso
02a0: 6e 2d 57 65 73 6c 65 79 0a 2a 2a 20 20 20 20 20  n-Wesley.**     
02b0: 50 75 62 6c 69 73 68 69 6e 67 20 43 6f 6d 70 61  Publishing Compa
02c0: 6e 79 2c 20 52 65 61 64 69 6e 67 2c 20 4d 61 73  ny, Reading, Mas
02d0: 73 61 63 68 75 73 65 74 74 73 2e 0a 2a 2a 0a 2a  sachusetts..**.*
02e0: 2a 20 54 68 65 20 62 61 73 69 63 20 69 64 65 61  * The basic idea
02f0: 20 69 73 20 74 68 61 74 20 65 61 63 68 20 70 61   is that each pa
0300: 67 65 20 6f 66 20 74 68 65 20 66 69 6c 65 20 63  ge of the file c
0310: 6f 6e 74 61 69 6e 73 20 4e 20 64 61 74 61 62 61  ontains N databa
0320: 73 65 0a 2a 2a 20 65 6e 74 72 69 65 73 20 61 6e  se.** entries an
0330: 64 20 4e 2b 31 20 70 6f 69 6e 74 65 72 73 20 74  d N+1 pointers t
0340: 6f 20 73 75 62 70 61 67 65 73 2e 0a 2a 2a 0a 2a  o subpages..**.*
0350: 2a 20 20 20 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 2d 0a 2a 2a 20 20 20 7c 20 20 50 74 72  ----.**   |  Ptr
03a0: 28 30 29 20 7c 20 4b 65 79 28 30 29 20 7c 20 50  (0) | Key(0) | P
03b0: 74 72 28 31 29 20 7c 20 4b 65 79 28 31 29 20 7c  tr(1) | Key(1) |
03c0: 20 2e 2e 2e 20 7c 20 4b 65 79 28 4e 2d 31 29 20   ... | Key(N-1) 
03d0: 7c 20 50 74 72 28 4e 29 20 7c 0a 2a 2a 20 20 20  | 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 2d  ----------------
0420: 0a 2a 2a 0a 2a 2a 20 41 6c 6c 20 6f 66 20 74 68  .**.** All of th
0430: 65 20 6b 65 79 73 20 6f 6e 20 74 68 65 20 70 61  e keys on the pa
0440: 67 65 20 74 68 61 74 20 50 74 72 28 30 29 20 70  ge that Ptr(0) p
0450: 6f 69 6e 74 73 20 74 6f 20 68 61 76 65 20 76 61  oints to have va
0460: 6c 75 65 73 20 6c 65 73 73 0a 2a 2a 20 74 68 61  lues less.** tha
0470: 6e 20 4b 65 79 28 30 29 2e 20 20 41 6c 6c 20 6f  n Key(0).  All o
0480: 66 20 74 68 65 20 6b 65 79 73 20 6f 6e 20 70 61  f the keys on pa
0490: 67 65 20 50 74 72 28 31 29 20 61 6e 64 20 69 74  ge Ptr(1) and it
04a0: 73 20 73 75 62 70 61 67 65 73 20 68 61 76 65 0a  s subpages have.
04b0: 2a 2a 20 76 61 6c 75 65 73 20 67 72 65 61 74 65  ** values greate
04c0: 72 20 74 68 61 6e 20 4b 65 79 28 30 29 20 61 6e  r than Key(0) an
04d0: 64 20 6c 65 73 73 20 74 68 61 6e 20 4b 65 79 28  d less than Key(
04e0: 31 29 2e 20 20 41 6c 6c 20 6f 66 20 74 68 65 20  1).  All of the 
04f0: 6b 65 79 73 0a 2a 2a 20 6f 6e 20 50 74 72 28 4e  keys.** on Ptr(N
0500: 29 20 61 6e 64 20 69 74 73 20 73 75 62 70 61 67  ) and its subpag
0510: 65 73 20 68 61 76 65 20 76 61 6c 75 65 73 20 67  es have values g
0520: 72 65 61 74 65 72 20 74 68 61 6e 20 4b 65 79 28  reater than Key(
0530: 4e 2d 31 29 2e 20 20 41 6e 64 0a 2a 2a 20 73 6f  N-1).  And.** so
0540: 20 66 6f 72 74 68 2e 0a 2a 2a 0a 2a 2a 20 46 69   forth..**.** Fi
0550: 6e 64 69 6e 67 20 61 20 70 61 72 74 69 63 75 6c  nding a particul
0560: 61 72 20 6b 65 79 20 72 65 71 75 69 72 65 73 20  ar key requires 
0570: 72 65 61 64 69 6e 67 20 4f 28 6c 6f 67 28 4d 29  reading O(log(M)
0580: 29 20 70 61 67 65 73 20 66 72 6f 6d 20 74 68 65  ) pages from the
0590: 20 0a 2a 2a 20 64 69 73 6b 20 77 68 65 72 65 20   .** disk where 
05a0: 4d 20 69 73 20 74 68 65 20 6e 75 6d 62 65 72 20  M is the number 
05b0: 6f 66 20 65 6e 74 72 69 65 73 20 69 6e 20 74 68  of entries in th
05c0: 65 20 74 72 65 65 2e 0a 2a 2a 0a 2a 2a 20 49 6e  e tree..**.** In
05d0: 20 74 68 69 73 20 69 6d 70 6c 65 6d 65 6e 74 61   this implementa
05e0: 74 69 6f 6e 2c 20 61 20 73 69 6e 67 6c 65 20 66  tion, a single f
05f0: 69 6c 65 20 63 61 6e 20 68 6f 6c 64 20 6f 6e 65  ile can hold one
0600: 20 6f 72 20 6d 6f 72 65 20 73 65 70 61 72 61 74   or more separat
0610: 65 20 0a 2a 2a 20 42 54 72 65 65 73 2e 20 20 45  e .** BTrees.  E
0620: 61 63 68 20 42 54 72 65 65 20 69 73 20 69 64 65  ach BTree is ide
0630: 6e 74 69 66 69 65 64 20 62 79 20 74 68 65 20 69  ntified by the i
0640: 6e 64 65 78 20 6f 66 20 69 74 73 20 72 6f 6f 74  ndex of its root
0650: 20 70 61 67 65 2e 20 20 54 68 65 0a 2a 2a 20 6b   page.  The.** k
0660: 65 79 20 61 6e 64 20 64 61 74 61 20 66 6f 72 20  ey and data for 
0670: 61 6e 79 20 65 6e 74 72 79 20 61 72 65 20 63 6f  any entry are co
0680: 6d 62 69 6e 65 64 20 74 6f 20 66 6f 72 6d 20 74  mbined to form t
0690: 68 65 20 22 70 61 79 6c 6f 61 64 22 2e 20 20 41  he "payload".  A
06a0: 0a 2a 2a 20 66 69 78 65 64 20 61 6d 6f 75 6e 74  .** fixed amount
06b0: 20 6f 66 20 70 61 79 6c 6f 61 64 20 63 61 6e 20   of payload can 
06c0: 62 65 20 63 61 72 72 69 65 64 20 64 69 72 65 63  be carried direc
06d0: 74 6c 79 20 6f 6e 20 74 68 65 20 64 61 74 61 62  tly on the datab
06e0: 61 73 65 0a 2a 2a 20 70 61 67 65 2e 20 20 49 66  ase.** page.  If
06f0: 20 74 68 65 20 70 61 79 6c 6f 61 64 20 69 73 20   the payload is 
0700: 6c 61 72 67 65 72 20 74 68 61 6e 20 74 68 65 20  larger than the 
0710: 70 72 65 73 65 74 20 61 6d 6f 75 6e 74 20 74 68  preset amount th
0720: 65 6e 20 73 75 72 70 6c 75 73 0a 2a 2a 20 62 79  en surplus.** by
0730: 74 65 73 20 61 72 65 20 73 74 6f 72 65 64 20 6f  tes are stored o
0740: 6e 20 6f 76 65 72 66 6c 6f 77 20 70 61 67 65 73  n overflow pages
0750: 2e 20 20 54 68 65 20 70 61 79 6c 6f 61 64 20 66  .  The payload f
0760: 6f 72 20 61 6e 20 65 6e 74 72 79 0a 2a 2a 20 61  or an entry.** a
0770: 6e 64 20 74 68 65 20 70 72 65 63 65 64 69 6e 67  nd the preceding
0780: 20 70 6f 69 6e 74 65 72 20 61 72 65 20 63 6f 6d   pointer are com
0790: 62 69 6e 65 64 20 74 6f 20 66 6f 72 6d 20 61 20  bined to form a 
07a0: 22 43 65 6c 6c 22 2e 20 20 45 61 63 68 20 0a 2a  "Cell".  Each .*
07b0: 2a 20 70 61 67 65 20 68 61 73 20 61 20 73 6d 61  * page has a sma
07c0: 6c 6c 20 68 65 61 64 65 72 20 77 68 69 63 68 20  ll header which 
07d0: 63 6f 6e 74 61 69 6e 73 20 74 68 65 20 50 74 72  contains the Ptr
07e0: 28 4e 29 20 70 6f 69 6e 74 65 72 20 61 6e 64 20  (N) pointer and 
07f0: 6f 74 68 65 72 0a 2a 2a 20 69 6e 66 6f 72 6d 61  other.** informa
0800: 74 69 6f 6e 20 73 75 63 68 20 61 73 20 74 68 65  tion such as the
0810: 20 73 69 7a 65 20 6f 66 20 6b 65 79 20 61 6e 64   size of key and
0820: 20 64 61 74 61 2e 0a 2a 2a 0a 2a 2a 20 46 4f 52   data..**.** FOR
0830: 4d 41 54 20 44 45 54 41 49 4c 53 0a 2a 2a 0a 2a  MAT DETAILS.**.*
0840: 2a 20 54 68 65 20 66 69 6c 65 20 69 73 20 64 69  * The file is di
0850: 76 69 64 65 64 20 69 6e 74 6f 20 70 61 67 65 73  vided into pages
0860: 2e 20 20 54 68 65 20 66 69 72 73 74 20 70 61 67  .  The first pag
0870: 65 20 69 73 20 63 61 6c 6c 65 64 20 70 61 67 65  e is called page
0880: 20 31 2c 0a 2a 2a 20 74 68 65 20 73 65 63 6f 6e   1,.** the secon
0890: 64 20 69 73 20 70 61 67 65 20 32 2c 20 61 6e 64  d is page 2, and
08a0: 20 73 6f 20 66 6f 72 74 68 2e 20 20 41 20 70 61   so forth.  A pa
08b0: 67 65 20 6e 75 6d 62 65 72 20 6f 66 20 7a 65 72  ge number of zer
08c0: 6f 20 69 6e 64 69 63 61 74 65 73 0a 2a 2a 20 22  o indicates.** "
08d0: 6e 6f 20 73 75 63 68 20 70 61 67 65 22 2e 20 20  no such page".  
08e0: 54 68 65 20 70 61 67 65 20 73 69 7a 65 20 63 61  The page size ca
08f0: 6e 20 62 65 20 61 6e 79 74 68 69 6e 67 20 62 65  n be anything be
0900: 74 77 65 65 6e 20 35 31 32 20 61 6e 64 20 36 35  tween 512 and 65
0910: 35 33 36 2e 0a 2a 2a 20 45 61 63 68 20 70 61 67  536..** Each pag
0920: 65 20 63 61 6e 20 62 65 20 65 69 74 68 65 72 20  e can be either 
0930: 61 20 62 74 72 65 65 20 70 61 67 65 2c 20 61 20  a btree page, a 
0940: 66 72 65 65 6c 69 73 74 20 70 61 67 65 20 6f 72  freelist page or
0950: 20 61 6e 20 6f 76 65 72 66 6c 6f 77 0a 2a 2a 20   an overflow.** 
0960: 70 61 67 65 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20  page..**.** The 
0970: 66 69 72 73 74 20 70 61 67 65 20 69 73 20 61 6c  first page is al
0980: 77 61 79 73 20 61 20 62 74 72 65 65 20 70 61 67  ways a btree pag
0990: 65 2e 20 20 54 68 65 20 66 69 72 73 74 20 31 30  e.  The first 10
09a0: 30 20 62 79 74 65 73 20 6f 66 20 74 68 65 20 66  0 bytes of the f
09b0: 69 72 73 74 0a 2a 2a 20 70 61 67 65 20 63 6f 6e  irst.** page con
09c0: 74 61 69 6e 20 61 20 73 70 65 63 69 61 6c 20 68  tain a special h
09d0: 65 61 64 65 72 20 28 74 68 65 20 22 66 69 6c 65  eader (the "file
09e0: 20 68 65 61 64 65 72 22 29 20 74 68 61 74 20 64   header") that d
09f0: 65 73 63 72 69 62 65 73 20 74 68 65 20 66 69 6c  escribes the fil
0a00: 65 2e 0a 2a 2a 20 54 68 65 20 66 6f 72 6d 61 74  e..** The format
0a10: 20 6f 66 20 74 68 65 20 66 69 6c 65 20 68 65 61   of the file hea
0a20: 64 65 72 20 69 73 20 61 73 20 66 6f 6c 6c 6f 77  der is as follow
0a30: 73 3a 0a 2a 2a 0a 2a 2a 20 20 20 4f 46 46 53 45  s:.**.**   OFFSE
0a40: 54 20 20 20 53 49 5a 45 20 20 20 20 44 45 53 43  T   SIZE    DESC
0a50: 52 49 50 54 49 4f 4e 0a 2a 2a 20 20 20 20 20 20  RIPTION.**      
0a60: 30 20 20 20 20 20 20 31 36 20 20 20 20 20 48 65  0      16     He
0a70: 61 64 65 72 20 73 74 72 69 6e 67 3a 20 22 53 51  ader string: "SQ
0a80: 4c 69 74 65 20 66 6f 72 6d 61 74 20 33 5c 30 30  Lite format 3\00
0a90: 30 22 0a 2a 2a 20 20 20 20 20 31 36 20 20 20 20  0".**     16    
0aa0: 20 20 20 32 20 20 20 20 20 50 61 67 65 20 73 69     2     Page si
0ab0: 7a 65 20 69 6e 20 62 79 74 65 73 2e 20 20 0a 2a  ze in bytes.  .*
0ac0: 2a 20 20 20 20 20 31 38 20 20 20 20 20 20 20 31  *     18       1
0ad0: 20 20 20 20 20 46 69 6c 65 20 66 6f 72 6d 61 74       File format
0ae0: 20 77 72 69 74 65 20 76 65 72 73 69 6f 6e 0a 2a   write version.*
0af0: 2a 20 20 20 20 20 31 39 20 20 20 20 20 20 20 31  *     19       1
0b00: 20 20 20 20 20 46 69 6c 65 20 66 6f 72 6d 61 74       File format
0b10: 20 72 65 61 64 20 76 65 72 73 69 6f 6e 0a 2a 2a   read version.**
0b20: 20 20 20 20 20 32 30 20 20 20 20 20 20 20 31 20       20       1 
0b30: 20 20 20 20 42 79 74 65 73 20 6f 66 20 75 6e 75      Bytes of unu
0b40: 73 65 64 20 73 70 61 63 65 20 61 74 20 74 68 65  sed space at the
0b50: 20 65 6e 64 20 6f 66 20 65 61 63 68 20 70 61 67   end of each pag
0b60: 65 0a 2a 2a 20 20 20 20 20 32 31 20 20 20 20 20  e.**     21     
0b70: 20 20 31 20 20 20 20 20 4d 61 78 20 65 6d 62 65    1     Max embe
0b80: 64 64 65 64 20 70 61 79 6c 6f 61 64 20 66 72 61  dded payload fra
0b90: 63 74 69 6f 6e 0a 2a 2a 20 20 20 20 20 32 32 20  ction.**     22 
0ba0: 20 20 20 20 20 20 31 20 20 20 20 20 4d 69 6e 20        1     Min 
0bb0: 65 6d 62 65 64 64 65 64 20 70 61 79 6c 6f 61 64  embedded payload
0bc0: 20 66 72 61 63 74 69 6f 6e 0a 2a 2a 20 20 20 20   fraction.**    
0bd0: 20 32 33 20 20 20 20 20 20 20 31 20 20 20 20 20   23       1     
0be0: 4d 69 6e 20 6c 65 61 66 20 70 61 79 6c 6f 61 64  Min leaf payload
0bf0: 20 66 72 61 63 74 69 6f 6e 0a 2a 2a 20 20 20 20   fraction.**    
0c00: 20 32 34 20 20 20 20 20 20 20 34 20 20 20 20 20   24       4     
0c10: 46 69 6c 65 20 63 68 61 6e 67 65 20 63 6f 75 6e  File change coun
0c20: 74 65 72 0a 2a 2a 20 20 20 20 20 32 38 20 20 20  ter.**     28   
0c30: 20 20 20 20 34 20 20 20 20 20 52 65 73 65 72 76      4     Reserv
0c40: 65 64 20 66 6f 72 20 66 75 74 75 72 65 20 75 73  ed for future us
0c50: 65 0a 2a 2a 20 20 20 20 20 33 32 20 20 20 20 20  e.**     32     
0c60: 20 20 34 20 20 20 20 20 46 69 72 73 74 20 66 72    4     First fr
0c70: 65 65 6c 69 73 74 20 70 61 67 65 0a 2a 2a 20 20  eelist page.**  
0c80: 20 20 20 33 36 20 20 20 20 20 20 20 34 20 20 20     36       4   
0c90: 20 20 4e 75 6d 62 65 72 20 6f 66 20 66 72 65 65    Number of free
0ca0: 6c 69 73 74 20 70 61 67 65 73 20 69 6e 20 74 68  list pages in th
0cb0: 65 20 66 69 6c 65 0a 2a 2a 20 20 20 20 20 34 30  e file.**     40
0cc0: 20 20 20 20 20 20 36 30 20 20 20 20 20 31 35 20        60     15 
0cd0: 34 2d 62 79 74 65 20 6d 65 74 61 20 76 61 6c 75  4-byte meta valu
0ce0: 65 73 20 70 61 73 73 65 64 20 74 6f 20 68 69 67  es passed to hig
0cf0: 68 65 72 20 6c 61 79 65 72 73 0a 2a 2a 0a 2a 2a  her layers.**.**
0d00: 20 20 20 20 20 34 30 20 20 20 20 20 20 20 34 20       40       4 
0d10: 20 20 20 20 53 63 68 65 6d 61 20 63 6f 6f 6b 69      Schema cooki
0d20: 65 0a 2a 2a 20 20 20 20 20 34 34 20 20 20 20 20  e.**     44     
0d30: 20 20 34 20 20 20 20 20 46 69 6c 65 20 66 6f 72    4     File for
0d40: 6d 61 74 20 6f 66 20 73 63 68 65 6d 61 20 6c 61  mat of schema la
0d50: 79 65 72 0a 2a 2a 20 20 20 20 20 34 38 20 20 20  yer.**     48   
0d60: 20 20 20 20 34 20 20 20 20 20 53 69 7a 65 20 6f      4     Size o
0d70: 66 20 70 61 67 65 20 63 61 63 68 65 0a 2a 2a 20  f page cache.** 
0d80: 20 20 20 20 35 32 20 20 20 20 20 20 20 34 20 20      52       4  
0d90: 20 20 20 4c 61 72 67 65 73 74 20 72 6f 6f 74 2d     Largest root-
0da0: 70 61 67 65 20 28 61 75 74 6f 2f 69 6e 63 72 5f  page (auto/incr_
0db0: 76 61 63 75 75 6d 29 0a 2a 2a 20 20 20 20 20 35  vacuum).**     5
0dc0: 36 20 20 20 20 20 20 20 34 20 20 20 20 20 31 3d  6       4     1=
0dd0: 55 54 46 2d 38 20 32 3d 55 54 46 31 36 6c 65 20  UTF-8 2=UTF16le 
0de0: 33 3d 55 54 46 31 36 62 65 0a 2a 2a 20 20 20 20  3=UTF16be.**    
0df0: 20 36 30 20 20 20 20 20 20 20 34 20 20 20 20 20   60       4     
0e00: 55 73 65 72 20 76 65 72 73 69 6f 6e 0a 2a 2a 20  User version.** 
0e10: 20 20 20 20 36 34 20 20 20 20 20 20 20 34 20 20      64       4  
0e20: 20 20 20 49 6e 63 72 65 6d 65 6e 74 61 6c 20 76     Incremental v
0e30: 61 63 75 75 6d 20 6d 6f 64 65 0a 2a 2a 20 20 20  acuum mode.**   
0e40: 20 20 36 38 20 20 20 20 20 20 20 34 20 20 20 20    68       4    
0e50: 20 75 6e 75 73 65 64 0a 2a 2a 20 20 20 20 20 37   unused.**     7
0e60: 32 20 20 20 20 20 20 20 34 20 20 20 20 20 75 6e  2       4     un
0e70: 75 73 65 64 0a 2a 2a 20 20 20 20 20 37 36 20 20  used.**     76  
0e80: 20 20 20 20 20 34 20 20 20 20 20 75 6e 75 73 65       4     unuse
0e90: 64 0a 2a 2a 0a 2a 2a 20 41 6c 6c 20 6f 66 20 74  d.**.** All of t
0ea0: 68 65 20 69 6e 74 65 67 65 72 20 76 61 6c 75 65  he integer value
0eb0: 73 20 61 72 65 20 62 69 67 2d 65 6e 64 69 61 6e  s are big-endian
0ec0: 20 28 6d 6f 73 74 20 73 69 67 6e 69 66 69 63 61   (most significa
0ed0: 6e 74 20 62 79 74 65 20 66 69 72 73 74 29 2e 0a  nt byte first)..
0ee0: 2a 2a 0a 2a 2a 20 54 68 65 20 66 69 6c 65 20 63  **.** The file c
0ef0: 68 61 6e 67 65 20 63 6f 75 6e 74 65 72 20 69 73  hange counter is
0f00: 20 69 6e 63 72 65 6d 65 6e 74 65 64 20 77 68 65   incremented whe
0f10: 6e 20 74 68 65 20 64 61 74 61 62 61 73 65 20 69  n the database i
0f20: 73 20 63 68 61 6e 67 65 64 0a 2a 2a 20 54 68 69  s changed.** Thi
0f30: 73 20 63 6f 75 6e 74 65 72 20 61 6c 6c 6f 77 73  s counter allows
0f40: 20 6f 74 68 65 72 20 70 72 6f 63 65 73 73 65 73   other processes
0f50: 20 74 6f 20 6b 6e 6f 77 20 77 68 65 6e 20 74 68   to know when th
0f60: 65 20 66 69 6c 65 20 68 61 73 20 63 68 61 6e 67  e file has chang
0f70: 65 64 0a 2a 2a 20 61 6e 64 20 74 68 75 73 20 77  ed.** and thus w
0f80: 68 65 6e 20 74 68 65 79 20 6e 65 65 64 20 74 6f  hen they need to
0f90: 20 66 6c 75 73 68 20 74 68 65 69 72 20 63 61 63   flush their cac
0fa0: 68 65 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 6d 61  he..**.** The ma
0fb0: 78 20 65 6d 62 65 64 64 65 64 20 70 61 79 6c 6f  x embedded paylo
0fc0: 61 64 20 66 72 61 63 74 69 6f 6e 20 69 73 20 74  ad fraction is t
0fd0: 68 65 20 61 6d 6f 75 6e 74 20 6f 66 20 74 68 65  he amount of the
0fe0: 20 74 6f 74 61 6c 20 75 73 61 62 6c 65 0a 2a 2a   total usable.**
0ff0: 20 73 70 61 63 65 20 69 6e 20 61 20 70 61 67 65   space in a page
1000: 20 74 68 61 74 20 63 61 6e 20 62 65 20 63 6f 6e   that can be con
1010: 73 75 6d 65 64 20 62 79 20 61 20 73 69 6e 67 6c  sumed by a singl
1020: 65 20 63 65 6c 6c 20 66 6f 72 20 73 74 61 6e 64  e cell for stand
1030: 61 72 64 0a 2a 2a 20 42 2d 74 72 65 65 20 28 6e  ard.** B-tree (n
1040: 6f 6e 2d 4c 45 41 46 44 41 54 41 29 20 74 61 62  on-LEAFDATA) tab
1050: 6c 65 73 2e 20 20 41 20 76 61 6c 75 65 20 6f 66  les.  A value of
1060: 20 32 35 35 20 6d 65 61 6e 73 20 31 30 30 25 2e   255 means 100%.
1070: 20 20 54 68 65 20 64 65 66 61 75 6c 74 0a 2a 2a    The default.**
1080: 20 69 73 20 74 6f 20 6c 69 6d 69 74 20 74 68 65   is to limit the
1090: 20 6d 61 78 69 6d 75 6d 20 63 65 6c 6c 20 73 69   maximum cell si
10a0: 7a 65 20 73 6f 20 74 68 61 74 20 61 74 20 6c 65  ze so that at le
10b0: 61 73 74 20 34 20 63 65 6c 6c 73 20 77 69 6c 6c  ast 4 cells will
10c0: 20 66 69 74 0a 2a 2a 20 6f 6e 20 6f 6e 65 20 70   fit.** on one p
10d0: 61 67 65 2e 20 20 54 68 75 73 20 74 68 65 20 64  age.  Thus the d
10e0: 65 66 61 75 6c 74 20 6d 61 78 20 65 6d 62 65 64  efault max embed
10f0: 64 65 64 20 70 61 79 6c 6f 61 64 20 66 72 61 63  ded payload frac
1100: 74 69 6f 6e 20 69 73 20 36 34 2e 0a 2a 2a 0a 2a  tion is 64..**.*
1110: 2a 20 49 66 20 74 68 65 20 70 61 79 6c 6f 61 64  * If the payload
1120: 20 66 6f 72 20 61 20 63 65 6c 6c 20 69 73 20 6c   for a cell is l
1130: 61 72 67 65 72 20 74 68 61 6e 20 74 68 65 20 6d  arger than the m
1140: 61 78 20 70 61 79 6c 6f 61 64 2c 20 74 68 65 6e  ax payload, then
1150: 20 65 78 74 72 61 0a 2a 2a 20 70 61 79 6c 6f 61   extra.** payloa
1160: 64 20 69 73 20 73 70 69 6c 6c 65 64 20 74 6f 20  d is spilled to 
1170: 6f 76 65 72 66 6c 6f 77 20 70 61 67 65 73 2e 20  overflow pages. 
1180: 20 4f 6e 63 65 20 61 6e 20 6f 76 65 72 66 6c 6f   Once an overflo
1190: 77 20 70 61 67 65 20 69 73 20 61 6c 6c 6f 63 61  w page is alloca
11a0: 74 65 64 2c 0a 2a 2a 20 61 73 20 6d 61 6e 79 20  ted,.** as many 
11b0: 62 79 74 65 73 20 61 73 20 70 6f 73 73 69 62 6c  bytes as possibl
11c0: 65 20 61 72 65 20 6d 6f 76 65 64 20 69 6e 74 6f  e are moved into
11d0: 20 74 68 65 20 6f 76 65 72 66 6c 6f 77 20 70 61   the overflow pa
11e0: 67 65 73 20 77 69 74 68 6f 75 74 20 6c 65 74 74  ges without lett
11f0: 69 6e 67 0a 2a 2a 20 74 68 65 20 63 65 6c 6c 20  ing.** the cell 
1200: 73 69 7a 65 20 64 72 6f 70 20 62 65 6c 6f 77 20  size drop below 
1210: 74 68 65 20 6d 69 6e 20 65 6d 62 65 64 64 65 64  the min embedded
1220: 20 70 61 79 6c 6f 61 64 20 66 72 61 63 74 69 6f   payload fractio
1230: 6e 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 6d 69 6e  n..**.** The min
1240: 20 6c 65 61 66 20 70 61 79 6c 6f 61 64 20 66 72   leaf payload fr
1250: 61 63 74 69 6f 6e 20 69 73 20 6c 69 6b 65 20 74  action is like t
1260: 68 65 20 6d 69 6e 20 65 6d 62 65 64 64 65 64 20  he min embedded 
1270: 70 61 79 6c 6f 61 64 20 66 72 61 63 74 69 6f 6e  payload fraction
1280: 0a 2a 2a 20 65 78 63 65 70 74 20 74 68 61 74 20  .** except that 
1290: 69 74 20 61 70 70 6c 69 65 73 20 74 6f 20 6c 65  it applies to le
12a0: 61 66 20 6e 6f 64 65 73 20 69 6e 20 61 20 4c 45  af nodes in a LE
12b0: 41 46 44 41 54 41 20 74 72 65 65 2e 20 20 54 68  AFDATA tree.  Th
12c0: 65 20 6d 61 78 69 6d 75 6d 0a 2a 2a 20 70 61 79  e maximum.** pay
12d0: 6c 6f 61 64 20 66 72 61 63 74 69 6f 6e 20 66 6f  load fraction fo
12e0: 72 20 61 20 4c 45 41 46 44 41 54 41 20 74 72 65  r a LEAFDATA tre
12f0: 65 20 69 73 20 61 6c 77 61 79 73 20 31 30 30 25  e is always 100%
1300: 20 28 6f 72 20 32 35 35 29 20 61 6e 64 20 69 74   (or 255) and it
1310: 0a 2a 2a 20 6e 6f 74 20 73 70 65 63 69 66 69 65  .** not specifie
1320: 64 20 69 6e 20 74 68 65 20 68 65 61 64 65 72 2e  d in the header.
1330: 0a 2a 2a 0a 2a 2a 20 45 61 63 68 20 62 74 72 65  .**.** Each btre
1340: 65 20 70 61 67 65 73 20 69 73 20 64 69 76 69 64  e pages is divid
1350: 65 64 20 69 6e 74 6f 20 74 68 72 65 65 20 73 65  ed into three se
1360: 63 74 69 6f 6e 73 3a 20 20 54 68 65 20 68 65 61  ctions:  The hea
1370: 64 65 72 2c 20 74 68 65 0a 2a 2a 20 63 65 6c 6c  der, the.** cell
1380: 20 70 6f 69 6e 74 65 72 20 61 72 72 61 79 2c 20   pointer array, 
1390: 61 6e 64 20 74 68 65 20 63 65 6c 6c 20 63 6f 6e  and the cell con
13a0: 74 65 6e 74 20 61 72 65 61 2e 20 20 50 61 67 65  tent area.  Page
13b0: 20 31 20 61 6c 73 6f 20 68 61 73 20 61 20 31 30   1 also has a 10
13c0: 30 2d 62 79 74 65 0a 2a 2a 20 66 69 6c 65 20 68  0-byte.** file h
13d0: 65 61 64 65 72 20 74 68 61 74 20 6f 63 63 75 72  eader that occur
13e0: 73 20 62 65 66 6f 72 65 20 74 68 65 20 70 61 67  s before the pag
13f0: 65 20 68 65 61 64 65 72 2e 0a 2a 2a 0a 2a 2a 20  e header..**.** 
1400: 20 20 20 20 20 7c 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d       |----------
1410: 2d 2d 2d 2d 2d 2d 7c 0a 2a 2a 20 20 20 20 20 20  ------|.**      
1420: 7c 20 66 69 6c 65 20 68 65 61 64 65 72 20 20 20  | file header   
1430: 20 7c 20 20 20 31 30 30 20 62 79 74 65 73 2e 20   |   100 bytes. 
1440: 20 50 61 67 65 20 31 20 6f 6e 6c 79 2e 0a 2a 2a   Page 1 only..**
1450: 20 20 20 20 20 20 7c 2d 2d 2d 2d 2d 2d 2d 2d 2d        |---------
1460: 2d 2d 2d 2d 2d 2d 2d 7c 0a 2a 2a 20 20 20 20 20  -------|.**     
1470: 20 7c 20 70 61 67 65 20 68 65 61 64 65 72 20 20   | page header  
1480: 20 20 7c 20 20 20 38 20 62 79 74 65 73 20 66 6f    |   8 bytes fo
1490: 72 20 6c 65 61 76 65 73 2e 20 20 31 32 20 62 79  r leaves.  12 by
14a0: 74 65 73 20 66 6f 72 20 69 6e 74 65 72 69 6f 72  tes for interior
14b0: 20 6e 6f 64 65 73 0a 2a 2a 20 20 20 20 20 20 7c   nodes.**      |
14c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
14d0: 7c 0a 2a 2a 20 20 20 20 20 20 7c 20 63 65 6c 6c  |.**      | cell
14e0: 20 70 6f 69 6e 74 65 72 20 20 20 7c 20 20 20 7c   pointer   |   |
14f0: 20 20 32 20 62 79 74 65 73 20 70 65 72 20 63 65    2 bytes per ce
1500: 6c 6c 2e 20 20 53 6f 72 74 65 64 20 6f 72 64 65  ll.  Sorted orde
1510: 72 2e 0a 2a 2a 20 20 20 20 20 20 7c 20 61 72 72  r..**      | arr
1520: 61 79 20 20 20 20 20 20 20 20 20 20 7c 20 20 20  ay          |   
1530: 7c 20 20 47 72 6f 77 73 20 64 6f 77 6e 77 61 72  |  Grows downwar
1540: 64 0a 2a 2a 20 20 20 20 20 20 7c 20 20 20 20 20  d.**      |     
1550: 20 20 20 20 20 20 20 20 20 20 20 7c 20 20 20 76             |   v
1560: 0a 2a 2a 20 20 20 20 20 20 7c 2d 2d 2d 2d 2d 2d  .**      |------
1570: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 7c 0a 2a 2a 20 20  ----------|.**  
1580: 20 20 20 20 7c 20 75 6e 61 6c 6c 6f 63 61 74 65      | unallocate
1590: 64 20 20 20 20 7c 0a 2a 2a 20 20 20 20 20 20 7c  d    |.**      |
15a0: 20 73 70 61 63 65 20 20 20 20 20 20 20 20 20 20   space          
15b0: 7c 0a 2a 2a 20 20 20 20 20 20 7c 2d 2d 2d 2d 2d  |.**      |-----
15c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 7c 20 20 20 5e  -----------|   ^
15d0: 20 20 47 72 6f 77 73 20 75 70 77 61 72 64 73 0a    Grows upwards.
15e0: 2a 2a 20 20 20 20 20 20 7c 20 63 65 6c 6c 20 63  **      | cell c
15f0: 6f 6e 74 65 6e 74 20 20 20 7c 20 20 20 7c 20 20  ontent   |   |  
1600: 41 72 62 69 74 72 61 72 79 20 6f 72 64 65 72 20  Arbitrary order 
1610: 69 6e 74 65 72 73 70 65 72 73 65 64 20 77 69 74  interspersed wit
1620: 68 20 66 72 65 65 62 6c 6f 63 6b 73 2e 0a 2a 2a  h freeblocks..**
1630: 20 20 20 20 20 20 7c 20 61 72 65 61 20 20 20 20        | area    
1640: 20 20 20 20 20 20 20 7c 20 20 20 7c 20 20 61 6e         |   |  an
1650: 64 20 66 72 65 65 20 73 70 61 63 65 20 66 72 61  d free space fra
1660: 67 6d 65 6e 74 73 2e 0a 2a 2a 20 20 20 20 20 20  gments..**      
1670: 7c 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  |---------------
1680: 2d 7c 0a 2a 2a 0a 2a 2a 20 54 68 65 20 70 61 67  -|.**.** The pag
1690: 65 20 68 65 61 64 65 72 73 20 6c 6f 6f 6b 73 20  e headers looks 
16a0: 6c 69 6b 65 20 74 68 69 73 3a 0a 2a 2a 0a 2a 2a  like this:.**.**
16b0: 20 20 20 4f 46 46 53 45 54 20 20 20 53 49 5a 45     OFFSET   SIZE
16c0: 20 20 20 20 20 44 45 53 43 52 49 50 54 49 4f 4e       DESCRIPTION
16d0: 0a 2a 2a 20 20 20 20 20 20 30 20 20 20 20 20 20  .**      0      
16e0: 20 31 20 20 20 20 20 20 46 6c 61 67 73 2e 20 31   1      Flags. 1
16f0: 3a 20 69 6e 74 6b 65 79 2c 20 32 3a 20 7a 65 72  : intkey, 2: zer
1700: 6f 64 61 74 61 2c 20 34 3a 20 6c 65 61 66 64 61  odata, 4: leafda
1710: 74 61 2c 20 38 3a 20 6c 65 61 66 0a 2a 2a 20 20  ta, 8: leaf.**  
1720: 20 20 20 20 31 20 20 20 20 20 20 20 32 20 20 20      1       2   
1730: 20 20 20 62 79 74 65 20 6f 66 66 73 65 74 20 74     byte offset t
1740: 6f 20 74 68 65 20 66 69 72 73 74 20 66 72 65 65  o the first free
1750: 62 6c 6f 63 6b 0a 2a 2a 20 20 20 20 20 20 33 20  block.**      3 
1760: 20 20 20 20 20 20 32 20 20 20 20 20 20 6e 75 6d        2      num
1770: 62 65 72 20 6f 66 20 63 65 6c 6c 73 20 6f 6e 20  ber of cells on 
1780: 74 68 69 73 20 70 61 67 65 0a 2a 2a 20 20 20 20  this page.**    
1790: 20 20 35 20 20 20 20 20 20 20 32 20 20 20 20 20    5       2     
17a0: 20 66 69 72 73 74 20 62 79 74 65 20 6f 66 20 74   first byte of t
17b0: 68 65 20 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 20  he cell content 
17c0: 61 72 65 61 0a 2a 2a 20 20 20 20 20 20 37 20 20  area.**      7  
17d0: 20 20 20 20 20 31 20 20 20 20 20 20 6e 75 6d 62       1      numb
17e0: 65 72 20 6f 66 20 66 72 61 67 6d 65 6e 74 65 64  er of fragmented
17f0: 20 66 72 65 65 20 62 79 74 65 73 0a 2a 2a 20 20   free bytes.**  
1800: 20 20 20 20 38 20 20 20 20 20 20 20 34 20 20 20      8       4   
1810: 20 20 20 52 69 67 68 74 20 63 68 69 6c 64 20 28     Right child (
1820: 74 68 65 20 50 74 72 28 4e 29 20 76 61 6c 75 65  the Ptr(N) value
1830: 29 2e 20 20 4f 6d 69 74 74 65 64 20 6f 6e 20 6c  ).  Omitted on l
1840: 65 61 76 65 73 2e 0a 2a 2a 0a 2a 2a 20 54 68 65  eaves..**.** The
1850: 20 66 6c 61 67 73 20 64 65 66 69 6e 65 20 74 68   flags define th
1860: 65 20 66 6f 72 6d 61 74 20 6f 66 20 74 68 69 73  e format of this
1870: 20 62 74 72 65 65 20 70 61 67 65 2e 20 20 54 68   btree page.  Th
1880: 65 20 6c 65 61 66 20 66 6c 61 67 20 6d 65 61 6e  e leaf flag mean
1890: 73 20 74 68 61 74 0a 2a 2a 20 74 68 69 73 20 70  s that.** this p
18a0: 61 67 65 20 68 61 73 20 6e 6f 20 63 68 69 6c 64  age has no child
18b0: 72 65 6e 2e 20 20 54 68 65 20 7a 65 72 6f 64 61  ren.  The zeroda
18c0: 74 61 20 66 6c 61 67 20 6d 65 61 6e 73 20 74 68  ta flag means th
18d0: 61 74 20 74 68 69 73 20 70 61 67 65 20 63 61 72  at this page car
18e0: 72 69 65 73 0a 2a 2a 20 6f 6e 6c 79 20 6b 65 79  ries.** only key
18f0: 73 20 61 6e 64 20 6e 6f 20 64 61 74 61 2e 20 20  s and no data.  
1900: 54 68 65 20 69 6e 74 6b 65 79 20 66 6c 61 67 20  The intkey flag 
1910: 6d 65 61 6e 73 20 74 68 61 74 20 74 68 65 20 6b  means that the k
1920: 65 79 20 69 73 20 61 20 69 6e 74 65 67 65 72 0a  ey is a integer.
1930: 2a 2a 20 77 68 69 63 68 20 69 73 20 73 74 6f 72  ** which is stor
1940: 65 64 20 69 6e 20 74 68 65 20 6b 65 79 20 73 69  ed in the key si
1950: 7a 65 20 65 6e 74 72 79 20 6f 66 20 74 68 65 20  ze entry of the 
1960: 63 65 6c 6c 20 68 65 61 64 65 72 20 72 61 74 68  cell header rath
1970: 65 72 20 74 68 61 6e 20 69 6e 0a 2a 2a 20 74 68  er than in.** th
1980: 65 20 70 61 79 6c 6f 61 64 20 61 72 65 61 2e 0a  e payload area..
1990: 2a 2a 0a 2a 2a 20 54 68 65 20 63 65 6c 6c 20 70  **.** The cell p
19a0: 6f 69 6e 74 65 72 20 61 72 72 61 79 20 62 65 67  ointer array beg
19b0: 69 6e 73 20 6f 6e 20 74 68 65 20 66 69 72 73 74  ins on the first
19c0: 20 62 79 74 65 20 61 66 74 65 72 20 74 68 65 20   byte after the 
19d0: 70 61 67 65 20 68 65 61 64 65 72 2e 0a 2a 2a 20  page header..** 
19e0: 54 68 65 20 63 65 6c 6c 20 70 6f 69 6e 74 65 72  The cell pointer
19f0: 20 61 72 72 61 79 20 63 6f 6e 74 61 69 6e 73 20   array contains 
1a00: 7a 65 72 6f 20 6f 72 20 6d 6f 72 65 20 32 2d 62  zero or more 2-b
1a10: 79 74 65 20 6e 75 6d 62 65 72 73 20 77 68 69 63  yte numbers whic
1a20: 68 20 61 72 65 0a 2a 2a 20 6f 66 66 73 65 74 73  h are.** offsets
1a30: 20 66 72 6f 6d 20 74 68 65 20 62 65 67 69 6e 6e   from the beginn
1a40: 69 6e 67 20 6f 66 20 74 68 65 20 70 61 67 65 20  ing of the page 
1a50: 74 6f 20 74 68 65 20 63 65 6c 6c 20 63 6f 6e 74  to the cell cont
1a60: 65 6e 74 20 69 6e 20 74 68 65 20 63 65 6c 6c 0a  ent in the cell.
1a70: 2a 2a 20 63 6f 6e 74 65 6e 74 20 61 72 65 61 2e  ** content area.
1a80: 20 20 54 68 65 20 63 65 6c 6c 20 70 6f 69 6e 74    The cell point
1a90: 65 72 73 20 6f 63 63 75 72 20 69 6e 20 73 6f 72  ers occur in sor
1aa0: 74 65 64 20 6f 72 64 65 72 2e 20 20 54 68 65 20  ted order.  The 
1ab0: 73 79 73 74 65 6d 20 73 74 72 69 76 65 73 0a 2a  system strives.*
1ac0: 2a 20 74 6f 20 6b 65 65 70 20 66 72 65 65 20 73  * to keep free s
1ad0: 70 61 63 65 20 61 66 74 65 72 20 74 68 65 20 6c  pace after the l
1ae0: 61 73 74 20 63 65 6c 6c 20 70 6f 69 6e 74 65 72  ast cell pointer
1af0: 20 73 6f 20 74 68 61 74 20 6e 65 77 20 63 65 6c   so that new cel
1b00: 6c 73 20 63 61 6e 0a 2a 2a 20 62 65 20 65 61 73  ls can.** be eas
1b10: 69 6c 79 20 61 64 64 65 64 20 77 69 74 68 6f 75  ily added withou
1b20: 74 20 68 61 76 69 6e 67 20 74 6f 20 64 65 66 72  t having to defr
1b30: 61 67 6d 65 6e 74 20 74 68 65 20 70 61 67 65 2e  agment the page.
1b40: 0a 2a 2a 0a 2a 2a 20 43 65 6c 6c 20 63 6f 6e 74  .**.** Cell cont
1b50: 65 6e 74 20 69 73 20 73 74 6f 72 65 64 20 61 74  ent is stored at
1b60: 20 74 68 65 20 76 65 72 79 20 65 6e 64 20 6f 66   the very end of
1b70: 20 74 68 65 20 70 61 67 65 20 61 6e 64 20 67 72   the page and gr
1b80: 6f 77 73 20 74 6f 77 61 72 64 20 74 68 65 0a 2a  ows toward the.*
1b90: 2a 20 62 65 67 69 6e 6e 69 6e 67 20 6f 66 20 74  * beginning of t
1ba0: 68 65 20 70 61 67 65 2e 0a 2a 2a 0a 2a 2a 20 55  he page..**.** U
1bb0: 6e 75 73 65 64 20 73 70 61 63 65 20 77 69 74 68  nused space with
1bc0: 69 6e 20 74 68 65 20 63 65 6c 6c 20 63 6f 6e 74  in the cell cont
1bd0: 65 6e 74 20 61 72 65 61 20 69 73 20 63 6f 6c 6c  ent area is coll
1be0: 65 63 74 65 64 20 69 6e 74 6f 20 61 20 6c 69 6e  ected into a lin
1bf0: 6b 65 64 20 6c 69 73 74 20 6f 66 0a 2a 2a 20 66  ked list of.** f
1c00: 72 65 65 62 6c 6f 63 6b 73 2e 20 20 45 61 63 68  reeblocks.  Each
1c10: 20 66 72 65 65 62 6c 6f 63 6b 20 69 73 20 61 74   freeblock is at
1c20: 20 6c 65 61 73 74 20 34 20 62 79 74 65 73 20 69   least 4 bytes i
1c30: 6e 20 73 69 7a 65 2e 20 20 54 68 65 20 62 79 74  n size.  The byt
1c40: 65 20 6f 66 66 73 65 74 0a 2a 2a 20 74 6f 20 74  e offset.** to t
1c50: 68 65 20 66 69 72 73 74 20 66 72 65 65 62 6c 6f  he first freeblo
1c60: 63 6b 20 69 73 20 67 69 76 65 6e 20 69 6e 20 74  ck is given in t
1c70: 68 65 20 68 65 61 64 65 72 2e 20 20 46 72 65 65  he header.  Free
1c80: 62 6c 6f 63 6b 73 20 6f 63 63 75 72 20 69 6e 0a  blocks occur in.
1c90: 2a 2a 20 69 6e 63 72 65 61 73 69 6e 67 20 6f 72  ** increasing or
1ca0: 64 65 72 2e 20 20 42 65 63 61 75 73 65 20 61 20  der.  Because a 
1cb0: 66 72 65 65 62 6c 6f 63 6b 20 6d 75 73 74 20 62  freeblock must b
1cc0: 65 20 61 74 20 6c 65 61 73 74 20 34 20 62 79 74  e at least 4 byt
1cd0: 65 73 20 69 6e 20 73 69 7a 65 2c 0a 2a 2a 20 61  es in size,.** a
1ce0: 6e 79 20 67 72 6f 75 70 20 6f 66 20 33 20 6f 72  ny group of 3 or
1cf0: 20 66 65 77 65 72 20 75 6e 75 73 65 64 20 62 79   fewer unused by
1d00: 74 65 73 20 69 6e 20 74 68 65 20 63 65 6c 6c 20  tes in the cell 
1d10: 63 6f 6e 74 65 6e 74 20 61 72 65 61 20 63 61 6e  content area can
1d20: 6e 6f 74 0a 2a 2a 20 65 78 69 73 74 20 6f 6e 20  not.** exist on 
1d30: 74 68 65 20 66 72 65 65 62 6c 6f 63 6b 20 63 68  the freeblock ch
1d40: 61 69 6e 2e 20 20 41 20 67 72 6f 75 70 20 6f 66  ain.  A group of
1d50: 20 33 20 6f 72 20 66 65 77 65 72 20 66 72 65 65   3 or fewer free
1d60: 20 62 79 74 65 73 20 69 73 20 63 61 6c 6c 65 64   bytes is called
1d70: 0a 2a 2a 20 61 20 66 72 61 67 6d 65 6e 74 2e 20  .** a fragment. 
1d80: 20 54 68 65 20 74 6f 74 61 6c 20 6e 75 6d 62 65   The total numbe
1d90: 72 20 6f 66 20 62 79 74 65 73 20 69 6e 20 61 6c  r of bytes in al
1da0: 6c 20 66 72 61 67 6d 65 6e 74 73 20 69 73 20 72  l fragments is r
1db0: 65 63 6f 72 64 65 64 2e 0a 2a 2a 20 69 6e 20 74  ecorded..** in t
1dc0: 68 65 20 70 61 67 65 20 68 65 61 64 65 72 20 61  he page header a
1dd0: 74 20 6f 66 66 73 65 74 20 37 2e 0a 2a 2a 0a 2a  t offset 7..**.*
1de0: 2a 20 20 20 20 53 49 5a 45 20 20 20 20 44 45 53  *    SIZE    DES
1df0: 43 52 49 50 54 49 4f 4e 0a 2a 2a 20 20 20 20 20  CRIPTION.**     
1e00: 20 32 20 20 20 20 20 42 79 74 65 20 6f 66 66 73   2     Byte offs
1e10: 65 74 20 6f 66 20 74 68 65 20 6e 65 78 74 20 66  et of the next f
1e20: 72 65 65 62 6c 6f 63 6b 0a 2a 2a 20 20 20 20 20  reeblock.**     
1e30: 20 32 20 20 20 20 20 42 79 74 65 73 20 69 6e 20   2     Bytes in 
1e40: 74 68 69 73 20 66 72 65 65 62 6c 6f 63 6b 0a 2a  this freeblock.*
1e50: 2a 0a 2a 2a 20 43 65 6c 6c 73 20 61 72 65 20 6f  *.** Cells are o
1e60: 66 20 76 61 72 69 61 62 6c 65 20 6c 65 6e 67 74  f variable lengt
1e70: 68 2e 20 20 43 65 6c 6c 73 20 61 72 65 20 73 74  h.  Cells are st
1e80: 6f 72 65 64 20 69 6e 20 74 68 65 20 63 65 6c 6c  ored in the cell
1e90: 20 63 6f 6e 74 65 6e 74 20 61 72 65 61 20 61 74   content area at
1ea0: 0a 2a 2a 20 74 68 65 20 65 6e 64 20 6f 66 20 74  .** the end of t
1eb0: 68 65 20 70 61 67 65 2e 20 20 50 6f 69 6e 74 65  he page.  Pointe
1ec0: 72 73 20 74 6f 20 74 68 65 20 63 65 6c 6c 73 20  rs to the cells 
1ed0: 61 72 65 20 69 6e 20 74 68 65 20 63 65 6c 6c 20  are in the cell 
1ee0: 70 6f 69 6e 74 65 72 20 61 72 72 61 79 0a 2a 2a  pointer array.**
1ef0: 20 74 68 61 74 20 69 6d 6d 65 64 69 61 74 65 6c   that immediatel
1f00: 79 20 66 6f 6c 6c 6f 77 73 20 74 68 65 20 70 61  y follows the pa
1f10: 67 65 20 68 65 61 64 65 72 2e 20 20 43 65 6c 6c  ge header.  Cell
1f20: 73 20 69 73 20 6e 6f 74 20 6e 65 63 65 73 73 61  s is not necessa
1f30: 72 69 6c 79 0a 2a 2a 20 63 6f 6e 74 69 67 75 6f  rily.** contiguo
1f40: 75 73 20 6f 72 20 69 6e 20 6f 72 64 65 72 2c 20  us or in order, 
1f50: 62 75 74 20 63 65 6c 6c 20 70 6f 69 6e 74 65 72  but cell pointer
1f60: 73 20 61 72 65 20 63 6f 6e 74 69 67 75 6f 75 73  s are contiguous
1f70: 20 61 6e 64 20 69 6e 20 6f 72 64 65 72 2e 0a 2a   and in order..*
1f80: 2a 0a 2a 2a 20 43 65 6c 6c 20 63 6f 6e 74 65 6e  *.** Cell conten
1f90: 74 20 6d 61 6b 65 73 20 75 73 65 20 6f 66 20 76  t makes use of v
1fa0: 61 72 69 61 62 6c 65 20 6c 65 6e 67 74 68 20 69  ariable length i
1fb0: 6e 74 65 67 65 72 73 2e 20 20 41 20 76 61 72 69  ntegers.  A vari
1fc0: 61 62 6c 65 0a 2a 2a 20 6c 65 6e 67 74 68 20 69  able.** length i
1fd0: 6e 74 65 67 65 72 20 69 73 20 31 20 74 6f 20 39  nteger is 1 to 9
1fe0: 20 62 79 74 65 73 20 77 68 65 72 65 20 74 68 65   bytes where the
1ff0: 20 6c 6f 77 65 72 20 37 20 62 69 74 73 20 6f 66   lower 7 bits of
2000: 20 65 61 63 68 20 0a 2a 2a 20 62 79 74 65 20 61   each .** byte a
2010: 72 65 20 75 73 65 64 2e 20 20 54 68 65 20 69 6e  re used.  The in
2020: 74 65 67 65 72 20 63 6f 6e 73 69 73 74 73 20 6f  teger consists o
2030: 66 20 61 6c 6c 20 62 79 74 65 73 20 74 68 61 74  f all bytes that
2040: 20 68 61 76 65 20 62 69 74 20 38 20 73 65 74 20   have bit 8 set 
2050: 61 6e 64 0a 2a 2a 20 74 68 65 20 66 69 72 73 74  and.** the first
2060: 20 62 79 74 65 20 77 69 74 68 20 62 69 74 20 38   byte with bit 8
2070: 20 63 6c 65 61 72 2e 20 20 54 68 65 20 6d 6f 73   clear.  The mos
2080: 74 20 73 69 67 6e 69 66 69 63 61 6e 74 20 62 79  t significant by
2090: 74 65 20 6f 66 20 74 68 65 20 69 6e 74 65 67 65  te of the intege
20a0: 72 0a 2a 2a 20 61 70 70 65 61 72 73 20 66 69 72  r.** appears fir
20b0: 73 74 2e 20 20 41 20 76 61 72 69 61 62 6c 65 2d  st.  A variable-
20c0: 6c 65 6e 67 74 68 20 69 6e 74 65 67 65 72 20 6d  length integer m
20d0: 61 79 20 6e 6f 74 20 62 65 20 6d 6f 72 65 20 74  ay not be more t
20e0: 68 61 6e 20 39 20 62 79 74 65 73 20 6c 6f 6e 67  han 9 bytes long
20f0: 2e 0a 2a 2a 20 41 73 20 61 20 73 70 65 63 69 61  ..** As a specia
2100: 6c 20 63 61 73 65 2c 20 61 6c 6c 20 38 20 62 79  l case, all 8 by
2110: 74 65 73 20 6f 66 20 74 68 65 20 39 74 68 20 62  tes of the 9th b
2120: 79 74 65 20 61 72 65 20 75 73 65 64 20 61 73 20  yte are used as 
2130: 64 61 74 61 2e 20 20 54 68 69 73 0a 2a 2a 20 61  data.  This.** a
2140: 6c 6c 6f 77 73 20 61 20 36 34 2d 62 69 74 20 69  llows a 64-bit i
2150: 6e 74 65 67 65 72 20 74 6f 20 62 65 20 65 6e 63  nteger to be enc
2160: 6f 64 65 64 20 69 6e 20 39 20 62 79 74 65 73 2e  oded in 9 bytes.
2170: 0a 2a 2a 0a 2a 2a 20 20 20 20 30 78 30 30 20 20  .**.**    0x00  
2180: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2190: 20 20 20 20 62 65 63 6f 6d 65 73 20 20 30 78 30      becomes  0x0
21a0: 30 30 30 30 30 30 30 0a 2a 2a 20 20 20 20 30 78  0000000.**    0x
21b0: 37 66 20 20 20 20 20 20 20 20 20 20 20 20 20 20  7f              
21c0: 20 20 20 20 20 20 20 20 62 65 63 6f 6d 65 73 20          becomes 
21d0: 20 30 78 30 30 30 30 30 30 37 66 0a 2a 2a 20 20   0x0000007f.**  
21e0: 20 20 30 78 38 31 20 30 78 30 30 20 20 20 20 20    0x81 0x00     
21f0: 20 20 20 20 20 20 20 20 20 20 20 20 62 65 63 6f              beco
2200: 6d 65 73 20 20 30 78 30 30 30 30 30 30 38 30 0a  mes  0x00000080.
2210: 2a 2a 20 20 20 20 30 78 38 32 20 30 78 30 30 20  **    0x82 0x00 
2220: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2230: 62 65 63 6f 6d 65 73 20 20 30 78 30 30 30 30 30  becomes  0x00000
2240: 31 30 30 0a 2a 2a 20 20 20 20 30 78 38 30 20 30  100.**    0x80 0
2250: 78 37 66 20 20 20 20 20 20 20 20 20 20 20 20 20  x7f             
2260: 20 20 20 20 62 65 63 6f 6d 65 73 20 20 30 78 30      becomes  0x0
2270: 30 30 30 30 30 37 66 0a 2a 2a 20 20 20 20 30 78  000007f.**    0x
2280: 38 61 20 30 78 39 31 20 30 78 64 31 20 30 78 61  8a 0x91 0xd1 0xa
2290: 63 20 30 78 37 38 20 20 62 65 63 6f 6d 65 73 20  c 0x78  becomes 
22a0: 20 30 78 31 32 33 34 35 36 37 38 0a 2a 2a 20 20   0x12345678.**  
22b0: 20 20 30 78 38 31 20 30 78 38 31 20 30 78 38 31    0x81 0x81 0x81
22c0: 20 30 78 38 31 20 30 78 30 31 20 20 62 65 63 6f   0x81 0x01  beco
22d0: 6d 65 73 20 20 30 78 31 30 32 30 34 30 38 31 0a  mes  0x10204081.
22e0: 2a 2a 0a 2a 2a 20 56 61 72 69 61 62 6c 65 20 6c  **.** Variable l
22f0: 65 6e 67 74 68 20 69 6e 74 65 67 65 72 73 20 61  ength integers a
2300: 72 65 20 75 73 65 64 20 66 6f 72 20 72 6f 77 69  re used for rowi
2310: 64 73 20 61 6e 64 20 74 6f 20 68 6f 6c 64 20 74  ds and to hold t
2320: 68 65 20 6e 75 6d 62 65 72 20 6f 66 0a 2a 2a 20  he number of.** 
2330: 62 79 74 65 73 20 6f 66 20 6b 65 79 20 61 6e 64  bytes of key and
2340: 20 64 61 74 61 20 69 6e 20 61 20 62 74 72 65 65   data in a btree
2350: 20 63 65 6c 6c 2e 0a 2a 2a 0a 2a 2a 20 54 68 65   cell..**.** The
2360: 20 63 6f 6e 74 65 6e 74 20 6f 66 20 61 20 63 65   content of a ce
2370: 6c 6c 20 6c 6f 6f 6b 73 20 6c 69 6b 65 20 74 68  ll looks like th
2380: 69 73 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 53 49 5a  is:.**.**    SIZ
2390: 45 20 20 20 20 44 45 53 43 52 49 50 54 49 4f 4e  E    DESCRIPTION
23a0: 0a 2a 2a 20 20 20 20 20 20 34 20 20 20 20 20 50  .**      4     P
23b0: 61 67 65 20 6e 75 6d 62 65 72 20 6f 66 20 74 68  age number of th
23c0: 65 20 6c 65 66 74 20 63 68 69 6c 64 2e 20 4f 6d  e left child. Om
23d0: 69 74 74 65 64 20 69 66 20 6c 65 61 66 20 66 6c  itted if leaf fl
23e0: 61 67 20 69 73 20 73 65 74 2e 0a 2a 2a 20 20 20  ag is set..**   
23f0: 20 20 76 61 72 20 20 20 20 4e 75 6d 62 65 72 20    var    Number 
2400: 6f 66 20 62 79 74 65 73 20 6f 66 20 64 61 74 61  of bytes of data
2410: 2e 20 4f 6d 69 74 74 65 64 20 69 66 20 74 68 65  . Omitted if the
2420: 20 7a 65 72 6f 64 61 74 61 20 66 6c 61 67 20 69   zerodata flag i
2430: 73 20 73 65 74 2e 0a 2a 2a 20 20 20 20 20 76 61  s set..**     va
2440: 72 20 20 20 20 4e 75 6d 62 65 72 20 6f 66 20 62  r    Number of b
2450: 79 74 65 73 20 6f 66 20 6b 65 79 2e 20 4f 72 20  ytes of key. Or 
2460: 74 68 65 20 6b 65 79 20 69 74 73 65 6c 66 20 69  the key itself i
2470: 66 20 69 6e 74 6b 65 79 20 66 6c 61 67 20 69 73  f intkey flag is
2480: 20 73 65 74 2e 0a 2a 2a 20 20 20 20 20 20 2a 20   set..**      * 
2490: 20 20 20 20 50 61 79 6c 6f 61 64 0a 2a 2a 20 20      Payload.**  
24a0: 20 20 20 20 34 20 20 20 20 20 46 69 72 73 74 20      4     First 
24b0: 70 61 67 65 20 6f 66 20 74 68 65 20 6f 76 65 72  page of the over
24c0: 66 6c 6f 77 20 63 68 61 69 6e 2e 20 20 4f 6d 69  flow chain.  Omi
24d0: 74 74 65 64 20 69 66 20 6e 6f 20 6f 76 65 72 66  tted if no overf
24e0: 6c 6f 77 0a 2a 2a 0a 2a 2a 20 4f 76 65 72 66 6c  low.**.** Overfl
24f0: 6f 77 20 70 61 67 65 73 20 66 6f 72 6d 20 61 20  ow pages form a 
2500: 6c 69 6e 6b 65 64 20 6c 69 73 74 2e 20 20 45 61  linked list.  Ea
2510: 63 68 20 70 61 67 65 20 65 78 63 65 70 74 20 74  ch page except t
2520: 68 65 20 6c 61 73 74 20 69 73 20 63 6f 6d 70 6c  he last is compl
2530: 65 74 65 6c 79 0a 2a 2a 20 66 69 6c 6c 65 64 20  etely.** filled 
2540: 77 69 74 68 20 64 61 74 61 20 28 70 61 67 65 73  with data (pages
2550: 69 7a 65 20 2d 20 34 20 62 79 74 65 73 29 2e 20  ize - 4 bytes). 
2560: 20 54 68 65 20 6c 61 73 74 20 70 61 67 65 20 63   The last page c
2570: 61 6e 20 68 61 76 65 20 61 73 20 6c 69 74 74 6c  an have as littl
2580: 65 0a 2a 2a 20 61 73 20 31 20 62 79 74 65 20 6f  e.** as 1 byte o
2590: 66 20 64 61 74 61 2e 0a 2a 2a 0a 2a 2a 20 20 20  f data..**.**   
25a0: 20 53 49 5a 45 20 20 20 20 44 45 53 43 52 49 50   SIZE    DESCRIP
25b0: 54 49 4f 4e 0a 2a 2a 20 20 20 20 20 20 34 20 20  TION.**      4  
25c0: 20 20 20 50 61 67 65 20 6e 75 6d 62 65 72 20 6f     Page number o
25d0: 66 20 6e 65 78 74 20 6f 76 65 72 66 6c 6f 77 20  f next overflow 
25e0: 70 61 67 65 0a 2a 2a 20 20 20 20 20 20 2a 20 20  page.**      *  
25f0: 20 20 20 44 61 74 61 0a 2a 2a 0a 2a 2a 20 46 72     Data.**.** Fr
2600: 65 65 6c 69 73 74 20 70 61 67 65 73 20 63 6f 6d  eelist pages com
2610: 65 20 69 6e 20 74 77 6f 20 73 75 62 74 79 70 65  e in two subtype
2620: 73 3a 20 74 72 75 6e 6b 20 70 61 67 65 73 20 61  s: trunk pages a
2630: 6e 64 20 6c 65 61 66 20 70 61 67 65 73 2e 20 20  nd leaf pages.  
2640: 54 68 65 0a 2a 2a 20 66 69 6c 65 20 68 65 61 64  The.** file head
2650: 65 72 20 70 6f 69 6e 74 73 20 74 6f 20 74 68 65  er points to the
2660: 20 66 69 72 73 74 20 69 6e 20 61 20 6c 69 6e 6b   first in a link
2670: 65 64 20 6c 69 73 74 20 6f 66 20 74 72 75 6e 6b  ed list of trunk
2680: 20 70 61 67 65 2e 20 20 45 61 63 68 20 74 72 75   page.  Each tru
2690: 6e 6b 0a 2a 2a 20 70 61 67 65 20 70 6f 69 6e 74  nk.** page point
26a0: 73 20 74 6f 20 6d 75 6c 74 69 70 6c 65 20 6c 65  s to multiple le
26b0: 61 66 20 70 61 67 65 73 2e 20 20 54 68 65 20 63  af pages.  The c
26c0: 6f 6e 74 65 6e 74 20 6f 66 20 61 20 6c 65 61 66  ontent of a leaf
26d0: 20 70 61 67 65 20 69 73 0a 2a 2a 20 75 6e 73 70   page is.** unsp
26e0: 65 63 69 66 69 65 64 2e 20 20 41 20 74 72 75 6e  ecified.  A trun
26f0: 6b 20 70 61 67 65 20 6c 6f 6f 6b 73 20 6c 69 6b  k page looks lik
2700: 65 20 74 68 69 73 3a 0a 2a 2a 0a 2a 2a 20 20 20  e this:.**.**   
2710: 20 53 49 5a 45 20 20 20 20 44 45 53 43 52 49 50   SIZE    DESCRIP
2720: 54 49 4f 4e 0a 2a 2a 20 20 20 20 20 20 34 20 20  TION.**      4  
2730: 20 20 20 50 61 67 65 20 6e 75 6d 62 65 72 20 6f     Page number o
2740: 66 20 6e 65 78 74 20 74 72 75 6e 6b 20 70 61 67  f next trunk pag
2750: 65 0a 2a 2a 20 20 20 20 20 20 34 20 20 20 20 20  e.**      4     
2760: 4e 75 6d 62 65 72 20 6f 66 20 6c 65 61 66 20 70  Number of leaf p
2770: 6f 69 6e 74 65 72 73 20 6f 6e 20 74 68 69 73 20  ointers on this 
2780: 70 61 67 65 0a 2a 2a 20 20 20 20 20 20 2a 20 20  page.**      *  
2790: 20 20 20 7a 65 72 6f 20 6f 72 20 6d 6f 72 65 20     zero or more 
27a0: 70 61 67 65 73 20 6e 75 6d 62 65 72 73 20 6f 66  pages numbers of
27b0: 20 6c 65 61 76 65 73 0a 2a 2f 0a 23 69 6e 63 6c   leaves.*/.#incl
27c0: 75 64 65 20 22 73 71 6c 69 74 65 49 6e 74 2e 68  ude "sqliteInt.h
27d0: 22 0a 0a 0a 2f 2a 20 54 68 65 20 66 6f 6c 6c 6f  ".../* The follo
27e0: 77 69 6e 67 20 76 61 6c 75 65 20 69 73 20 74 68  wing value is th
27f0: 65 20 6d 61 78 69 6d 75 6d 20 63 65 6c 6c 20 73  e maximum cell s
2800: 69 7a 65 20 61 73 73 75 6d 69 6e 67 20 61 20 6d  ize assuming a m
2810: 61 78 69 6d 75 6d 20 70 61 67 65 0a 2a 2a 20 73  aximum page.** s
2820: 69 7a 65 20 67 69 76 65 20 61 62 6f 76 65 2e 0a  ize give above..
2830: 2a 2f 0a 23 64 65 66 69 6e 65 20 4d 58 5f 43 45  */.#define MX_CE
2840: 4c 4c 5f 53 49 5a 45 28 70 42 74 29 20 20 28 70  LL_SIZE(pBt)  (p
2850: 42 74 2d 3e 70 61 67 65 53 69 7a 65 2d 38 29 0a  Bt->pageSize-8).
2860: 0a 2f 2a 20 54 68 65 20 6d 61 78 69 6d 75 6d 20  ./* The maximum 
2870: 6e 75 6d 62 65 72 20 6f 66 20 63 65 6c 6c 73 20  number of cells 
2880: 6f 6e 20 61 20 73 69 6e 67 6c 65 20 70 61 67 65  on a single page
2890: 20 6f 66 20 74 68 65 20 64 61 74 61 62 61 73 65   of the database
28a0: 2e 20 20 54 68 69 73 0a 2a 2a 20 61 73 73 75 6d  .  This.** assum
28b0: 65 73 20 61 20 6d 69 6e 69 6d 75 6d 20 63 65 6c  es a minimum cel
28c0: 6c 20 73 69 7a 65 20 6f 66 20 36 20 62 79 74 65  l size of 6 byte
28d0: 73 20 20 28 34 20 62 79 74 65 73 20 66 6f 72 20  s  (4 bytes for 
28e0: 74 68 65 20 63 65 6c 6c 20 69 74 73 65 6c 66 0a  the cell itself.
28f0: 2a 2a 20 70 6c 75 73 20 32 20 62 79 74 65 73 20  ** plus 2 bytes 
2900: 66 6f 72 20 74 68 65 20 69 6e 64 65 78 20 74 6f  for the index to
2910: 20 74 68 65 20 63 65 6c 6c 20 69 6e 20 74 68 65   the cell in the
2920: 20 70 61 67 65 20 68 65 61 64 65 72 29 2e 20 20   page header).  
2930: 53 75 63 68 0a 2a 2a 20 73 6d 61 6c 6c 20 63 65  Such.** small ce
2940: 6c 6c 73 20 77 69 6c 6c 20 62 65 20 72 61 72 65  lls will be rare
2950: 2c 20 62 75 74 20 74 68 65 79 20 61 72 65 20 70  , but they are p
2960: 6f 73 73 69 62 6c 65 2e 0a 2a 2f 0a 23 64 65 66  ossible..*/.#def
2970: 69 6e 65 20 4d 58 5f 43 45 4c 4c 28 70 42 74 29  ine MX_CELL(pBt)
2980: 20 28 28 70 42 74 2d 3e 70 61 67 65 53 69 7a 65   ((pBt->pageSize
2990: 2d 38 29 2f 36 29 0a 0a 2f 2a 20 46 6f 72 77 61  -8)/6)../* Forwa
29a0: 72 64 20 64 65 63 6c 61 72 61 74 69 6f 6e 73 20  rd declarations 
29b0: 2a 2f 0a 74 79 70 65 64 65 66 20 73 74 72 75 63  */.typedef struc
29c0: 74 20 4d 65 6d 50 61 67 65 20 4d 65 6d 50 61 67  t MemPage MemPag
29d0: 65 3b 0a 74 79 70 65 64 65 66 20 73 74 72 75 63  e;.typedef struc
29e0: 74 20 42 74 4c 6f 63 6b 20 42 74 4c 6f 63 6b 3b  t BtLock BtLock;
29f0: 0a 0a 2f 2a 0a 2a 2a 20 54 68 69 73 20 69 73 20  ../*.** This is 
2a00: 61 20 6d 61 67 69 63 20 73 74 72 69 6e 67 20 74  a magic string t
2a10: 68 61 74 20 61 70 70 65 61 72 73 20 61 74 20 74  hat appears at t
2a20: 68 65 20 62 65 67 69 6e 6e 69 6e 67 20 6f 66 20  he beginning of 
2a30: 65 76 65 72 79 0a 2a 2a 20 53 51 4c 69 74 65 20  every.** SQLite 
2a40: 64 61 74 61 62 61 73 65 20 69 6e 20 6f 72 64 65  database in orde
2a50: 72 20 74 6f 20 69 64 65 6e 74 69 66 79 20 74 68  r to identify th
2a60: 65 20 66 69 6c 65 20 61 73 20 61 20 72 65 61 6c  e file as a real
2a70: 20 64 61 74 61 62 61 73 65 2e 0a 2a 2a 0a 2a 2a   database..**.**
2a80: 20 59 6f 75 20 63 61 6e 20 63 68 61 6e 67 65 20   You can change 
2a90: 74 68 69 73 20 76 61 6c 75 65 20 61 74 20 63 6f  this value at co
2aa0: 6d 70 69 6c 65 2d 74 69 6d 65 20 62 79 20 73 70  mpile-time by sp
2ab0: 65 63 69 66 79 69 6e 67 20 61 0a 2a 2a 20 2d 44  ecifying a.** -D
2ac0: 53 51 4c 49 54 45 5f 46 49 4c 45 5f 48 45 41 44  SQLITE_FILE_HEAD
2ad0: 45 52 3d 22 2e 2e 2e 22 20 6f 6e 20 74 68 65 20  ER="..." on the 
2ae0: 63 6f 6d 70 69 6c 65 72 20 63 6f 6d 6d 61 6e 64  compiler command
2af0: 2d 6c 69 6e 65 2e 20 20 54 68 65 0a 2a 2a 20 68  -line.  The.** h
2b00: 65 61 64 65 72 20 6d 75 73 74 20 62 65 20 65 78  eader must be ex
2b10: 61 63 74 6c 79 20 31 36 20 62 79 74 65 73 20 69  actly 16 bytes i
2b20: 6e 63 6c 75 64 69 6e 67 20 74 68 65 20 7a 65 72  ncluding the zer
2b30: 6f 2d 74 65 72 6d 69 6e 61 74 6f 72 20 73 6f 0a  o-terminator so.
2b40: 2a 2a 20 74 68 65 20 73 74 72 69 6e 67 20 69 74  ** the string it
2b50: 73 65 6c 66 20 73 68 6f 75 6c 64 20 62 65 20 31  self should be 1
2b60: 35 20 63 68 61 72 61 63 74 65 72 73 20 6c 6f 6e  5 characters lon
2b70: 67 2e 20 20 49 66 20 79 6f 75 20 63 68 61 6e 67  g.  If you chang
2b80: 65 0a 2a 2a 20 74 68 65 20 68 65 61 64 65 72 2c  e.** the header,
2b90: 20 74 68 65 6e 20 79 6f 75 72 20 63 75 73 74 6f   then your custo
2ba0: 6d 20 6c 69 62 72 61 72 79 20 77 69 6c 6c 20 6e  m library will n
2bb0: 6f 74 20 62 65 20 61 62 6c 65 20 74 6f 20 72 65  ot be able to re
2bc0: 61 64 20 0a 2a 2a 20 64 61 74 61 62 61 73 65 73  ad .** databases
2bd0: 20 67 65 6e 65 72 61 74 65 64 20 62 79 20 74 68   generated by th
2be0: 65 20 73 74 61 6e 64 61 72 64 20 74 6f 6f 6c 73  e standard tools
2bf0: 20 61 6e 64 20 74 68 65 20 73 74 61 6e 64 61 72   and the standar
2c00: 64 20 74 6f 6f 6c 73 0a 2a 2a 20 77 69 6c 6c 20  d tools.** will 
2c10: 6e 6f 74 20 62 65 20 61 62 6c 65 20 74 6f 20 72  not be able to r
2c20: 65 61 64 20 64 61 74 61 62 61 73 65 73 20 63 72  ead databases cr
2c30: 65 61 74 65 64 20 62 79 20 79 6f 75 72 20 63 75  eated by your cu
2c40: 73 74 6f 6d 20 6c 69 62 72 61 72 79 2e 0a 2a 2f  stom library..*/
2c50: 0a 23 69 66 6e 64 65 66 20 53 51 4c 49 54 45 5f  .#ifndef SQLITE_
2c60: 46 49 4c 45 5f 48 45 41 44 45 52 20 2f 2a 20 31  FILE_HEADER /* 1
2c70: 32 33 34 35 36 37 38 39 20 31 32 33 34 35 36 20  23456789 123456 
2c80: 2a 2f 0a 23 20 20 64 65 66 69 6e 65 20 53 51 4c  */.#  define SQL
2c90: 49 54 45 5f 46 49 4c 45 5f 48 45 41 44 45 52 20  ITE_FILE_HEADER 
2ca0: 22 53 51 4c 69 74 65 20 66 6f 72 6d 61 74 20 33  "SQLite format 3
2cb0: 22 0a 23 65 6e 64 69 66 0a 0a 2f 2a 0a 2a 2a 20  ".#endif../*.** 
2cc0: 50 61 67 65 20 74 79 70 65 20 66 6c 61 67 73 2e  Page type flags.
2cd0: 20 20 41 6e 20 4f 52 65 64 20 63 6f 6d 62 69 6e    An ORed combin
2ce0: 61 74 69 6f 6e 20 6f 66 20 74 68 65 73 65 20 66  ation of these f
2cf0: 6c 61 67 73 20 61 70 70 65 61 72 20 61 73 20 74  lags appear as t
2d00: 68 65 0a 2a 2a 20 66 69 72 73 74 20 62 79 74 65  he.** first byte
2d10: 20 6f 66 20 6f 6e 2d 64 69 73 6b 20 69 6d 61 67   of on-disk imag
2d20: 65 20 6f 66 20 65 76 65 72 79 20 42 54 72 65 65  e of every BTree
2d30: 20 70 61 67 65 2e 0a 2a 2f 0a 23 64 65 66 69 6e   page..*/.#defin
2d40: 65 20 50 54 46 5f 49 4e 54 4b 45 59 20 20 20 20  e PTF_INTKEY    
2d50: 30 78 30 31 0a 23 64 65 66 69 6e 65 20 50 54 46  0x01.#define PTF
2d60: 5f 5a 45 52 4f 44 41 54 41 20 20 30 78 30 32 0a  _ZERODATA  0x02.
2d70: 23 64 65 66 69 6e 65 20 50 54 46 5f 4c 45 41 46  #define PTF_LEAF
2d80: 44 41 54 41 20 20 30 78 30 34 0a 23 64 65 66 69  DATA  0x04.#defi
2d90: 6e 65 20 50 54 46 5f 4c 45 41 46 20 20 20 20 20  ne PTF_LEAF     
2da0: 20 30 78 30 38 0a 0a 2f 2a 0a 2a 2a 20 41 73 20   0x08../*.** As 
2db0: 65 61 63 68 20 70 61 67 65 20 6f 66 20 74 68 65  each page of the
2dc0: 20 66 69 6c 65 20 69 73 20 6c 6f 61 64 65 64 20   file is loaded 
2dd0: 69 6e 74 6f 20 6d 65 6d 6f 72 79 2c 20 61 6e 20  into memory, an 
2de0: 69 6e 73 74 61 6e 63 65 20 6f 66 20 74 68 65 20  instance of the 
2df0: 66 6f 6c 6c 6f 77 69 6e 67 0a 2a 2a 20 73 74 72  following.** str
2e00: 75 63 74 75 72 65 20 69 73 20 61 70 70 65 6e 64  ucture is append
2e10: 65 64 20 61 6e 64 20 69 6e 69 74 69 61 6c 69 7a  ed and initializ
2e20: 65 64 20 74 6f 20 7a 65 72 6f 2e 20 20 54 68 69  ed to zero.  Thi
2e30: 73 20 73 74 72 75 63 74 75 72 65 20 73 74 6f 72  s structure stor
2e40: 65 73 0a 2a 2a 20 69 6e 66 6f 72 6d 61 74 69 6f  es.** informatio
2e50: 6e 20 61 62 6f 75 74 20 74 68 65 20 70 61 67 65  n about the page
2e60: 20 74 68 61 74 20 69 73 20 64 65 63 6f 64 65 64   that is decoded
2e70: 20 66 72 6f 6d 20 74 68 65 20 72 61 77 20 66 69   from the raw fi
2e80: 6c 65 20 70 61 67 65 2e 0a 2a 2a 0a 2a 2a 20 54  le page..**.** T
2e90: 68 65 20 70 50 61 72 65 6e 74 20 66 69 65 6c 64  he pParent field
2ea0: 20 70 6f 69 6e 74 73 20 62 61 63 6b 20 74 6f 20   points back to 
2eb0: 74 68 65 20 70 61 72 65 6e 74 20 70 61 67 65 2e  the parent page.
2ec0: 20 20 54 68 69 73 20 61 6c 6c 6f 77 73 20 75 73    This allows us
2ed0: 20 74 6f 0a 2a 2a 20 77 61 6c 6b 20 75 70 20 74   to.** walk up t
2ee0: 68 65 20 42 54 72 65 65 20 66 72 6f 6d 20 61 6e  he BTree from an
2ef0: 79 20 6c 65 61 66 20 74 6f 20 74 68 65 20 72 6f  y leaf to the ro
2f00: 6f 74 2e 20 20 43 61 72 65 20 6d 75 73 74 20 62  ot.  Care must b
2f10: 65 20 74 61 6b 65 6e 20 74 6f 0a 2a 2a 20 75 6e  e taken to.** un
2f20: 72 65 66 28 29 20 74 68 65 20 70 61 72 65 6e 74  ref() the parent
2f30: 20 70 61 67 65 20 70 6f 69 6e 74 65 72 20 77 68   page pointer wh
2f40: 65 6e 20 74 68 69 73 20 70 61 67 65 20 69 73 20  en this page is 
2f50: 6e 6f 20 6c 6f 6e 67 65 72 20 72 65 66 65 72 65  no longer refere
2f60: 6e 63 65 64 2e 0a 2a 2a 20 54 68 65 20 70 61 67  nced..** The pag
2f70: 65 44 65 73 74 72 75 63 74 6f 72 28 29 20 72 6f  eDestructor() ro
2f80: 75 74 69 6e 65 20 68 61 6e 64 6c 65 73 20 74 68  utine handles th
2f90: 61 74 20 63 68 6f 72 65 2e 0a 2a 2a 0a 2a 2a 20  at chore..**.** 
2fa0: 41 63 63 65 73 73 20 74 6f 20 61 6c 6c 20 66 69  Access to all fi
2fb0: 65 6c 64 73 20 6f 66 20 74 68 69 73 20 73 74 72  elds of this str
2fc0: 75 63 74 75 72 65 20 69 73 20 63 6f 6e 74 72 6f  ucture is contro
2fd0: 6c 6c 65 64 20 62 79 20 74 68 65 20 6d 75 74 65  lled by the mute
2fe0: 78 0a 2a 2a 20 73 74 6f 72 65 64 20 69 6e 20 4d  x.** stored in M
2ff0: 65 6d 50 61 67 65 2e 70 42 74 2d 3e 6d 75 74 65  emPage.pBt->mute
3000: 78 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 4d 65 6d  x..*/.struct Mem
3010: 50 61 67 65 20 7b 0a 20 20 75 38 20 69 73 49 6e  Page {.  u8 isIn
3020: 69 74 3b 20 20 20 20 20 20 20 20 20 20 20 2f 2a  it;           /*
3030: 20 54 72 75 65 20 69 66 20 70 72 65 76 69 6f 75   True if previou
3040: 73 6c 79 20 69 6e 69 74 69 61 6c 69 7a 65 64 2e  sly initialized.
3050: 20 4d 55 53 54 20 42 45 20 46 49 52 53 54 21 20   MUST BE FIRST! 
3060: 2a 2f 0a 20 20 75 38 20 6e 4f 76 65 72 66 6c 6f  */.  u8 nOverflo
3070: 77 3b 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d  w;        /* Num
3080: 62 65 72 20 6f 66 20 6f 76 65 72 66 6c 6f 77 20  ber of overflow 
3090: 63 65 6c 6c 20 62 6f 64 69 65 73 20 69 6e 20 61  cell bodies in a
30a0: 43 65 6c 6c 5b 5d 20 2a 2f 0a 20 20 75 38 20 69  Cell[] */.  u8 i
30b0: 6e 74 4b 65 79 3b 20 20 20 20 20 20 20 20 20 20  ntKey;          
30c0: 20 2f 2a 20 54 72 75 65 20 69 66 20 69 6e 74 6b   /* True if intk
30d0: 65 79 20 66 6c 61 67 20 69 73 20 73 65 74 20 2a  ey flag is set *
30e0: 2f 0a 20 20 75 38 20 6c 65 61 66 3b 20 20 20 20  /.  u8 leaf;    
30f0: 20 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65           /* True
3100: 20 69 66 20 6c 65 61 66 20 66 6c 61 67 20 69 73   if leaf flag is
3110: 20 73 65 74 20 2a 2f 0a 20 20 75 38 20 68 61 73   set */.  u8 has
3120: 44 61 74 61 3b 20 20 20 20 20 20 20 20 20 20 2f  Data;          /
3130: 2a 20 54 72 75 65 20 69 66 20 74 68 69 73 20 70  * True if this p
3140: 61 67 65 20 73 74 6f 72 65 73 20 64 61 74 61 20  age stores data 
3150: 2a 2f 0a 20 20 75 38 20 68 64 72 4f 66 66 73 65  */.  u8 hdrOffse
3160: 74 3b 20 20 20 20 20 20 20 20 2f 2a 20 31 30 30  t;        /* 100
3170: 20 66 6f 72 20 70 61 67 65 20 31 2e 20 20 30 20   for page 1.  0 
3180: 6f 74 68 65 72 77 69 73 65 20 2a 2f 0a 20 20 75  otherwise */.  u
3190: 38 20 63 68 69 6c 64 50 74 72 53 69 7a 65 3b 20  8 childPtrSize; 
31a0: 20 20 20 20 2f 2a 20 30 20 69 66 20 6c 65 61 66      /* 0 if leaf
31b0: 3d 3d 31 2e 20 20 34 20 69 66 20 6c 65 61 66 3d  ==1.  4 if leaf=
31c0: 3d 30 20 2a 2f 0a 20 20 75 31 36 20 6d 61 78 4c  =0 */.  u16 maxL
31d0: 6f 63 61 6c 3b 20 20 20 20 20 20 20 20 2f 2a 20  ocal;        /* 
31e0: 43 6f 70 79 20 6f 66 20 42 74 53 68 61 72 65 64  Copy of BtShared
31f0: 2e 6d 61 78 4c 6f 63 61 6c 20 6f 72 20 42 74 53  .maxLocal or BtS
3200: 68 61 72 65 64 2e 6d 61 78 4c 65 61 66 20 2a 2f  hared.maxLeaf */
3210: 0a 20 20 75 31 36 20 6d 69 6e 4c 6f 63 61 6c 3b  .  u16 minLocal;
3220: 20 20 20 20 20 20 20 20 2f 2a 20 43 6f 70 79 20          /* Copy 
3230: 6f 66 20 42 74 53 68 61 72 65 64 2e 6d 69 6e 4c  of BtShared.minL
3240: 6f 63 61 6c 20 6f 72 20 42 74 53 68 61 72 65 64  ocal or BtShared
3250: 2e 6d 69 6e 4c 65 61 66 20 2a 2f 0a 20 20 75 31  .minLeaf */.  u1
3260: 36 20 63 65 6c 6c 4f 66 66 73 65 74 3b 20 20 20  6 cellOffset;   
3270: 20 20 20 2f 2a 20 49 6e 64 65 78 20 69 6e 20 61     /* Index in a
3280: 44 61 74 61 20 6f 66 20 66 69 72 73 74 20 63 65  Data of first ce
3290: 6c 6c 20 70 6f 69 6e 74 65 72 20 2a 2f 0a 20 20  ll pointer */.  
32a0: 75 31 36 20 6e 46 72 65 65 3b 20 20 20 20 20 20  u16 nFree;      
32b0: 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f       /* Number o
32c0: 66 20 66 72 65 65 20 62 79 74 65 73 20 6f 6e 20  f free bytes on 
32d0: 74 68 65 20 70 61 67 65 20 2a 2f 0a 20 20 75 31  the page */.  u1
32e0: 36 20 6e 43 65 6c 6c 3b 20 20 20 20 20 20 20 20  6 nCell;        
32f0: 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20     /* Number of 
3300: 63 65 6c 6c 73 20 6f 6e 20 74 68 69 73 20 70 61  cells on this pa
3310: 67 65 2c 20 6c 6f 63 61 6c 20 61 6e 64 20 6f 76  ge, local and ov
3320: 66 6c 20 2a 2f 0a 20 20 75 31 36 20 6d 61 73 6b  fl */.  u16 mask
3330: 50 61 67 65 3b 20 20 20 20 20 20 20 20 2f 2a 20  Page;        /* 
3340: 4d 61 73 6b 20 66 6f 72 20 70 61 67 65 20 6f 66  Mask for page of
3350: 66 73 65 74 20 2a 2f 0a 20 20 73 74 72 75 63 74  fset */.  struct
3360: 20 5f 4f 76 66 6c 43 65 6c 6c 20 7b 20 20 20 2f   _OvflCell {   /
3370: 2a 20 43 65 6c 6c 73 20 74 68 61 74 20 77 69 6c  * Cells that wil
3380: 6c 20 6e 6f 74 20 66 69 74 20 6f 6e 20 61 44 61  l not fit on aDa
3390: 74 61 5b 5d 20 2a 2f 0a 20 20 20 20 75 38 20 2a  ta[] */.    u8 *
33a0: 70 43 65 6c 6c 3b 20 20 20 20 20 20 20 20 20 20  pCell;          
33b0: 2f 2a 20 50 6f 69 6e 74 65 72 73 20 74 6f 20 74  /* Pointers to t
33c0: 68 65 20 62 6f 64 79 20 6f 66 20 74 68 65 20 6f  he body of the o
33d0: 76 65 72 66 6c 6f 77 20 63 65 6c 6c 20 2a 2f 0a  verflow cell */.
33e0: 20 20 20 20 75 31 36 20 69 64 78 3b 20 20 20 20      u16 idx;    
33f0: 20 20 20 20 20 20 20 20 2f 2a 20 49 6e 73 65 72          /* Inser
3400: 74 20 74 68 69 73 20 63 65 6c 6c 20 62 65 66 6f  t this cell befo
3410: 72 65 20 69 64 78 2d 74 68 20 6e 6f 6e 2d 6f 76  re idx-th non-ov
3420: 65 72 66 6c 6f 77 20 63 65 6c 6c 20 2a 2f 0a 20  erflow cell */. 
3430: 20 7d 20 61 4f 76 66 6c 5b 35 5d 3b 0a 20 20 42   } aOvfl[5];.  B
3440: 74 53 68 61 72 65 64 20 2a 70 42 74 3b 20 20 20  tShared *pBt;   
3450: 20 20 20 20 2f 2a 20 50 6f 69 6e 74 65 72 20 74      /* Pointer t
3460: 6f 20 42 74 53 68 61 72 65 64 20 74 68 61 74 20  o BtShared that 
3470: 74 68 69 73 20 70 61 67 65 20 69 73 20 70 61 72  this page is par
3480: 74 20 6f 66 20 2a 2f 0a 20 20 75 38 20 2a 61 44  t of */.  u8 *aD
3490: 61 74 61 3b 20 20 20 20 20 20 20 20 20 20 20 2f  ata;           /
34a0: 2a 20 50 6f 69 6e 74 65 72 20 74 6f 20 64 69 73  * Pointer to dis
34b0: 6b 20 69 6d 61 67 65 20 6f 66 20 74 68 65 20 70  k image of the p
34c0: 61 67 65 20 64 61 74 61 20 2a 2f 0a 20 20 44 62  age data */.  Db
34d0: 50 61 67 65 20 2a 70 44 62 50 61 67 65 3b 20 20  Page *pDbPage;  
34e0: 20 20 20 2f 2a 20 50 61 67 65 72 20 70 61 67 65     /* Pager page
34f0: 20 68 61 6e 64 6c 65 20 2a 2f 0a 20 20 50 67 6e   handle */.  Pgn
3500: 6f 20 70 67 6e 6f 3b 20 20 20 20 20 20 20 20 20  o pgno;         
3510: 20 20 2f 2a 20 50 61 67 65 20 6e 75 6d 62 65 72    /* Page number
3520: 20 66 6f 72 20 74 68 69 73 20 70 61 67 65 20 2a   for this page *
3530: 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 20  /.};../*.** The 
3540: 69 6e 2d 6d 65 6d 6f 72 79 20 69 6d 61 67 65 20  in-memory image 
3550: 6f 66 20 61 20 64 69 73 6b 20 70 61 67 65 20 68  of a disk page h
3560: 61 73 20 74 68 65 20 61 75 78 69 6c 69 61 72 79  as the auxiliary
3570: 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 61 70 70   information app
3580: 65 6e 64 65 64 0a 2a 2a 20 74 6f 20 74 68 65 20  ended.** to the 
3590: 65 6e 64 2e 20 20 45 58 54 52 41 5f 53 49 5a 45  end.  EXTRA_SIZE
35a0: 20 69 73 20 74 68 65 20 6e 75 6d 62 65 72 20 6f   is the number o
35b0: 66 20 62 79 74 65 73 20 6f 66 20 73 70 61 63 65  f bytes of space
35c0: 20 6e 65 65 64 65 64 20 74 6f 20 68 6f 6c 64 0a   needed to hold.
35d0: 2a 2a 20 74 68 61 74 20 65 78 74 72 61 20 69 6e  ** that extra in
35e0: 66 6f 72 6d 61 74 69 6f 6e 2e 0a 2a 2f 0a 23 64  formation..*/.#d
35f0: 65 66 69 6e 65 20 45 58 54 52 41 5f 53 49 5a 45  efine EXTRA_SIZE
3600: 20 73 69 7a 65 6f 66 28 4d 65 6d 50 61 67 65 29   sizeof(MemPage)
3610: 0a 0a 2f 2a 0a 2a 2a 20 41 20 6c 69 6e 6b 65 64  ../*.** A linked
3620: 20 6c 69 73 74 20 6f 66 20 74 68 65 20 66 6f 6c   list of the fol
3630: 6c 6f 77 69 6e 67 20 73 74 72 75 63 74 75 72 65  lowing structure
3640: 73 20 69 73 20 73 74 6f 72 65 64 20 61 74 20 42  s is stored at B
3650: 74 53 68 61 72 65 64 2e 70 4c 6f 63 6b 2e 0a 2a  tShared.pLock..*
3660: 2a 20 4c 6f 63 6b 73 20 61 72 65 20 61 64 64 65  * Locks are adde
3670: 64 20 28 6f 72 20 75 70 67 72 61 64 65 64 20 66  d (or upgraded f
3680: 72 6f 6d 20 52 45 41 44 5f 4c 4f 43 4b 20 74 6f  rom READ_LOCK to
3690: 20 57 52 49 54 45 5f 4c 4f 43 4b 29 20 77 68 65   WRITE_LOCK) whe
36a0: 6e 20 61 20 63 75 72 73 6f 72 20 0a 2a 2a 20 69  n a cursor .** i
36b0: 73 20 6f 70 65 6e 65 64 20 6f 6e 20 74 68 65 20  s opened on the 
36c0: 74 61 62 6c 65 20 77 69 74 68 20 72 6f 6f 74 20  table with root 
36d0: 70 61 67 65 20 42 74 53 68 61 72 65 64 2e 69 54  page BtShared.iT
36e0: 61 62 6c 65 2e 20 4c 6f 63 6b 73 20 61 72 65 20  able. Locks are 
36f0: 72 65 6d 6f 76 65 64 0a 2a 2a 20 66 72 6f 6d 20  removed.** from 
3700: 74 68 69 73 20 6c 69 73 74 20 77 68 65 6e 20 61  this list when a
3710: 20 74 72 61 6e 73 61 63 74 69 6f 6e 20 69 73 20   transaction is 
3720: 63 6f 6d 6d 69 74 74 65 64 20 6f 72 20 72 6f 6c  committed or rol
3730: 6c 65 64 20 62 61 63 6b 2c 20 6f 72 20 77 68 65  led back, or whe
3740: 6e 0a 2a 2a 20 61 20 62 74 72 65 65 20 68 61 6e  n.** a btree han
3750: 64 6c 65 20 69 73 20 63 6c 6f 73 65 64 2e 0a 2a  dle is closed..*
3760: 2f 0a 73 74 72 75 63 74 20 42 74 4c 6f 63 6b 20  /.struct BtLock 
3770: 7b 0a 20 20 42 74 72 65 65 20 2a 70 42 74 72 65  {.  Btree *pBtre
3780: 65 3b 20 20 20 20 20 20 20 20 2f 2a 20 42 74 72  e;        /* Btr
3790: 65 65 20 68 61 6e 64 6c 65 20 68 6f 6c 64 69 6e  ee handle holdin
37a0: 67 20 74 68 69 73 20 6c 6f 63 6b 20 2a 2f 0a 20  g this lock */. 
37b0: 20 50 67 6e 6f 20 69 54 61 62 6c 65 3b 20 20 20   Pgno iTable;   
37c0: 20 20 20 20 20 20 20 2f 2a 20 52 6f 6f 74 20 70         /* Root p
37d0: 61 67 65 20 6f 66 20 74 61 62 6c 65 20 2a 2f 0a  age of table */.
37e0: 20 20 75 38 20 65 4c 6f 63 6b 3b 20 20 20 20 20    u8 eLock;     
37f0: 20 20 20 20 20 20 20 20 2f 2a 20 52 45 41 44 5f          /* READ_
3800: 4c 4f 43 4b 20 6f 72 20 57 52 49 54 45 5f 4c 4f  LOCK or WRITE_LO
3810: 43 4b 20 2a 2f 0a 20 20 42 74 4c 6f 63 6b 20 2a  CK */.  BtLock *
3820: 70 4e 65 78 74 3b 20 20 20 20 20 20 20 20 2f 2a  pNext;        /*
3830: 20 4e 65 78 74 20 69 6e 20 42 74 53 68 61 72 65   Next in BtShare
3840: 64 2e 70 4c 6f 63 6b 20 6c 69 73 74 20 2a 2f 0a  d.pLock list */.
3850: 7d 3b 0a 0a 2f 2a 20 43 61 6e 64 69 64 61 74 65  };../* Candidate
3860: 20 76 61 6c 75 65 73 20 66 6f 72 20 42 74 4c 6f   values for BtLo
3870: 63 6b 2e 65 4c 6f 63 6b 20 2a 2f 0a 23 64 65 66  ck.eLock */.#def
3880: 69 6e 65 20 52 45 41 44 5f 4c 4f 43 4b 20 20 20  ine READ_LOCK   
3890: 20 20 31 0a 23 64 65 66 69 6e 65 20 57 52 49 54    1.#define WRIT
38a0: 45 5f 4c 4f 43 4b 20 20 20 20 32 0a 0a 2f 2a 20  E_LOCK    2../* 
38b0: 41 20 42 74 72 65 65 20 68 61 6e 64 6c 65 0a 2a  A Btree handle.*
38c0: 2a 0a 2a 2a 20 41 20 64 61 74 61 62 61 73 65 20  *.** A database 
38d0: 63 6f 6e 6e 65 63 74 69 6f 6e 20 63 6f 6e 74 61  connection conta
38e0: 69 6e 73 20 61 20 70 6f 69 6e 74 65 72 20 74 6f  ins a pointer to
38f0: 20 61 6e 20 69 6e 73 74 61 6e 63 65 20 6f 66 0a   an instance of.
3900: 2a 2a 20 74 68 69 73 20 6f 62 6a 65 63 74 20 66  ** this object f
3910: 6f 72 20 65 76 65 72 79 20 64 61 74 61 62 61 73  or every databas
3920: 65 20 66 69 6c 65 20 74 68 61 74 20 69 74 20 68  e file that it h
3930: 61 73 20 6f 70 65 6e 2e 20 20 54 68 69 73 20 73  as open.  This s
3940: 74 72 75 63 74 75 72 65 0a 2a 2a 20 69 73 20 6f  tructure.** is o
3950: 70 61 71 75 65 20 74 6f 20 74 68 65 20 64 61 74  paque to the dat
3960: 61 62 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e  abase connection
3970: 2e 20 20 54 68 65 20 64 61 74 61 62 61 73 65 20  .  The database 
3980: 63 6f 6e 6e 65 63 74 69 6f 6e 20 63 61 6e 6e 6f  connection canno
3990: 74 0a 2a 2a 20 73 65 65 20 74 68 65 20 69 6e 74  t.** see the int
39a0: 65 72 6e 61 6c 73 20 6f 66 20 74 68 69 73 20 73  ernals of this s
39b0: 74 72 75 63 74 75 72 65 20 61 6e 64 20 6f 6e 6c  tructure and onl
39c0: 79 20 64 65 61 6c 73 20 77 69 74 68 20 70 6f 69  y deals with poi
39d0: 6e 74 65 72 73 20 74 6f 0a 2a 2a 20 74 68 69 73  nters to.** this
39e0: 20 73 74 72 75 63 74 75 72 65 2e 0a 2a 2a 0a 2a   structure..**.*
39f0: 2a 20 46 6f 72 20 73 6f 6d 65 20 64 61 74 61 62  * For some datab
3a00: 61 73 65 20 66 69 6c 65 73 2c 20 74 68 65 20 73  ase files, the s
3a10: 61 6d 65 20 75 6e 64 65 72 6c 79 69 6e 67 20 64  ame underlying d
3a20: 61 74 61 62 61 73 65 20 63 61 63 68 65 20 6d 69  atabase cache mi
3a30: 67 68 74 20 62 65 20 0a 2a 2a 20 73 68 61 72 65  ght be .** share
3a40: 64 20 62 65 74 77 65 65 6e 20 6d 75 6c 74 69 70  d between multip
3a50: 6c 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 73 2e 20  le connections. 
3a60: 20 49 6e 20 74 68 61 74 20 63 61 73 65 2c 20 65   In that case, e
3a70: 61 63 68 20 63 6f 6e 6e 65 63 74 69 6f 6e 0a 2a  ach connection.*
3a80: 2a 20 68 61 73 20 69 74 20 6f 77 6e 20 69 6e 73  * has it own ins
3a90: 74 61 6e 63 65 20 6f 66 20 74 68 69 73 20 6f 62  tance of this ob
3aa0: 6a 65 63 74 2e 20 20 42 75 74 20 65 61 63 68 20  ject.  But each 
3ab0: 69 6e 73 74 61 6e 63 65 20 6f 66 20 74 68 69 73  instance of this
3ac0: 20 6f 62 6a 65 63 74 0a 2a 2a 20 70 6f 69 6e 74   object.** point
3ad0: 73 20 74 6f 20 74 68 65 20 73 61 6d 65 20 42 74  s to the same Bt
3ae0: 53 68 61 72 65 64 20 6f 62 6a 65 63 74 2e 20 20  Shared object.  
3af0: 54 68 65 20 64 61 74 61 62 61 73 65 20 63 61 63  The database cac
3b00: 68 65 20 61 6e 64 20 74 68 65 0a 2a 2a 20 73 63  he and the.** sc
3b10: 68 65 6d 61 20 61 73 73 6f 63 69 61 74 65 64 20  hema associated 
3b20: 77 69 74 68 20 74 68 65 20 64 61 74 61 62 61 73  with the databas
3b30: 65 20 66 69 6c 65 20 61 72 65 20 61 6c 6c 20 63  e file are all c
3b40: 6f 6e 74 61 69 6e 65 64 20 77 69 74 68 69 6e 0a  ontained within.
3b50: 2a 2a 20 74 68 65 20 42 74 53 68 61 72 65 64 20  ** the BtShared 
3b60: 6f 62 6a 65 63 74 2e 0a 2a 2a 0a 2a 2a 20 41 6c  object..**.** Al
3b70: 6c 20 66 69 65 6c 64 73 20 69 6e 20 74 68 69 73  l fields in this
3b80: 20 73 74 72 75 63 74 75 72 65 20 61 72 65 20 61   structure are a
3b90: 63 63 65 73 73 65 64 20 75 6e 64 65 72 20 73 71  ccessed under sq
3ba0: 6c 69 74 65 33 2e 6d 75 74 65 78 2e 0a 2a 2a 20  lite3.mutex..** 
3bb0: 54 68 65 20 70 42 74 20 70 6f 69 6e 74 65 72 20  The pBt pointer 
3bc0: 69 74 73 65 6c 66 20 6d 61 79 20 6e 6f 74 20 62  itself may not b
3bd0: 65 20 63 68 61 6e 67 65 64 20 77 68 69 6c 65 20  e changed while 
3be0: 74 68 65 72 65 20 65 78 69 73 74 73 20 63 75 72  there exists cur
3bf0: 73 6f 72 73 20 0a 2a 2a 20 69 6e 20 74 68 65 20  sors .** in the 
3c00: 72 65 66 65 72 65 6e 63 65 64 20 42 74 53 68 61  referenced BtSha
3c10: 72 65 64 20 74 68 61 74 20 70 6f 69 6e 74 20 62  red that point b
3c20: 61 63 6b 20 74 6f 20 74 68 69 73 20 42 74 72 65  ack to this Btre
3c30: 65 20 73 69 6e 63 65 20 74 68 6f 73 65 0a 2a 2a  e since those.**
3c40: 20 63 75 72 73 6f 72 73 20 68 61 76 65 20 74 6f   cursors have to
3c50: 20 64 6f 20 67 6f 20 74 68 72 6f 75 67 68 20 74   do go through t
3c60: 68 69 73 20 42 74 72 65 65 20 74 6f 20 66 69 6e  his Btree to fin
3c70: 64 20 74 68 65 69 72 20 42 74 53 68 61 72 65 64  d their BtShared
3c80: 20 61 6e 64 0a 2a 2a 20 74 68 65 79 20 6f 66 74   and.** they oft
3c90: 65 6e 20 64 6f 20 73 6f 20 77 69 74 68 6f 75 74  en do so without
3ca0: 20 68 6f 6c 64 69 6e 67 20 73 71 6c 69 74 65 33   holding sqlite3
3cb0: 2e 6d 75 74 65 78 2e 0a 2a 2f 0a 73 74 72 75 63  .mutex..*/.struc
3cc0: 74 20 42 74 72 65 65 20 7b 0a 20 20 73 71 6c 69  t Btree {.  sqli
3cd0: 74 65 33 20 2a 64 62 3b 20 20 20 20 20 20 20 2f  te3 *db;       /
3ce0: 2a 20 54 68 65 20 64 61 74 61 62 61 73 65 20 63  * The database c
3cf0: 6f 6e 6e 65 63 74 69 6f 6e 20 68 6f 6c 64 69 6e  onnection holdin
3d00: 67 20 74 68 69 73 20 62 74 72 65 65 20 2a 2f 0a  g this btree */.
3d10: 20 20 42 74 53 68 61 72 65 64 20 2a 70 42 74 3b    BtShared *pBt;
3d20: 20 20 20 20 20 2f 2a 20 53 68 61 72 61 62 6c 65       /* Sharable
3d30: 20 63 6f 6e 74 65 6e 74 20 6f 66 20 74 68 69 73   content of this
3d40: 20 62 74 72 65 65 20 2a 2f 0a 20 20 75 38 20 69   btree */.  u8 i
3d50: 6e 54 72 61 6e 73 3b 20 20 20 20 20 20 20 20 2f  nTrans;        /
3d60: 2a 20 54 52 41 4e 53 5f 4e 4f 4e 45 2c 20 54 52  * TRANS_NONE, TR
3d70: 41 4e 53 5f 52 45 41 44 20 6f 72 20 54 52 41 4e  ANS_READ or TRAN
3d80: 53 5f 57 52 49 54 45 20 2a 2f 0a 20 20 75 38 20  S_WRITE */.  u8 
3d90: 73 68 61 72 61 62 6c 65 3b 20 20 20 20 20 20 20  sharable;       
3da0: 2f 2a 20 54 72 75 65 20 69 66 20 77 65 20 63 61  /* True if we ca
3db0: 6e 20 73 68 61 72 65 20 70 42 74 20 77 69 74 68  n share pBt with
3dc0: 20 61 6e 6f 74 68 65 72 20 64 62 20 2a 2f 0a 20   another db */. 
3dd0: 20 75 38 20 6c 6f 63 6b 65 64 3b 20 20 20 20 20   u8 locked;     
3de0: 20 20 20 20 2f 2a 20 54 72 75 65 20 69 66 20 64      /* True if d
3df0: 62 20 63 75 72 72 65 6e 74 6c 79 20 68 61 73 20  b currently has 
3e00: 70 42 74 20 6c 6f 63 6b 65 64 20 2a 2f 0a 20 20  pBt locked */.  
3e10: 69 6e 74 20 77 61 6e 74 54 6f 4c 6f 63 6b 3b 20  int wantToLock; 
3e20: 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20     /* Number of 
3e30: 6e 65 73 74 65 64 20 63 61 6c 6c 73 20 74 6f 20  nested calls to 
3e40: 73 71 6c 69 74 65 33 42 74 72 65 65 45 6e 74 65  sqlite3BtreeEnte
3e50: 72 28 29 20 2a 2f 0a 20 20 69 6e 74 20 6e 42 61  r() */.  int nBa
3e60: 63 6b 75 70 3b 20 20 20 20 20 20 20 2f 2a 20 4e  ckup;       /* N
3e70: 75 6d 62 65 72 20 6f 66 20 62 61 63 6b 75 70 20  umber of backup 
3e80: 6f 70 65 72 61 74 69 6f 6e 73 20 72 65 61 64 69  operations readi
3e90: 6e 67 20 74 68 69 73 20 62 74 72 65 65 20 2a 2f  ng this btree */
3ea0: 0a 20 20 42 74 72 65 65 20 2a 70 4e 65 78 74 3b  .  Btree *pNext;
3eb0: 20 20 20 20 20 20 2f 2a 20 4c 69 73 74 20 6f 66        /* List of
3ec0: 20 6f 74 68 65 72 20 73 68 61 72 61 62 6c 65 20   other sharable 
3ed0: 42 74 72 65 65 73 20 66 72 6f 6d 20 74 68 65 20  Btrees from the 
3ee0: 73 61 6d 65 20 64 62 20 2a 2f 0a 20 20 42 74 72  same db */.  Btr
3ef0: 65 65 20 2a 70 50 72 65 76 3b 20 20 20 20 20 20  ee *pPrev;      
3f00: 2f 2a 20 42 61 63 6b 20 70 6f 69 6e 74 65 72 20  /* Back pointer 
3f10: 6f 66 20 74 68 65 20 73 61 6d 65 20 6c 69 73 74  of the same list
3f20: 20 2a 2f 0a 23 69 66 6e 64 65 66 20 53 51 4c 49   */.#ifndef SQLI
3f30: 54 45 5f 4f 4d 49 54 5f 53 48 41 52 45 44 5f 43  TE_OMIT_SHARED_C
3f40: 41 43 48 45 0a 20 20 42 74 4c 6f 63 6b 20 6c 6f  ACHE.  BtLock lo
3f50: 63 6b 3b 20 20 20 20 20 20 20 2f 2a 20 4f 62 6a  ck;       /* Obj
3f60: 65 63 74 20 75 73 65 64 20 74 6f 20 6c 6f 63 6b  ect used to lock
3f70: 20 70 61 67 65 20 31 20 2a 2f 0a 23 65 6e 64 69   page 1 */.#endi
3f80: 66 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 42 74 72 65  f.};../*.** Btre
3f90: 65 2e 69 6e 54 72 61 6e 73 20 6d 61 79 20 74 61  e.inTrans may ta
3fa0: 6b 65 20 6f 6e 65 20 6f 66 20 74 68 65 20 66 6f  ke one of the fo
3fb0: 6c 6c 6f 77 69 6e 67 20 76 61 6c 75 65 73 2e 0a  llowing values..
3fc0: 2a 2a 0a 2a 2a 20 49 66 20 74 68 65 20 73 68 61  **.** If the sha
3fd0: 72 65 64 2d 64 61 74 61 20 65 78 74 65 6e 73 69  red-data extensi
3fe0: 6f 6e 20 69 73 20 65 6e 61 62 6c 65 64 2c 20 74  on is enabled, t
3ff0: 68 65 72 65 20 6d 61 79 20 62 65 20 6d 75 6c 74  here may be mult
4000: 69 70 6c 65 20 75 73 65 72 73 0a 2a 2a 20 6f 66  iple users.** of
4010: 20 74 68 65 20 42 74 72 65 65 20 73 74 72 75 63   the Btree struc
4020: 74 75 72 65 2e 20 41 74 20 6d 6f 73 74 20 6f 6e  ture. At most on
4030: 65 20 6f 66 20 74 68 65 73 65 20 6d 61 79 20 6f  e of these may o
4040: 70 65 6e 20 61 20 77 72 69 74 65 20 74 72 61 6e  pen a write tran
4050: 73 61 63 74 69 6f 6e 2c 0a 2a 2a 20 62 75 74 20  saction,.** but 
4060: 61 6e 79 20 6e 75 6d 62 65 72 20 6d 61 79 20 68  any number may h
4070: 61 76 65 20 61 63 74 69 76 65 20 72 65 61 64 20  ave active read 
4080: 74 72 61 6e 73 61 63 74 69 6f 6e 73 2e 0a 2a 2f  transactions..*/
4090: 0a 23 64 65 66 69 6e 65 20 54 52 41 4e 53 5f 4e  .#define TRANS_N
40a0: 4f 4e 45 20 20 30 0a 23 64 65 66 69 6e 65 20 54  ONE  0.#define T
40b0: 52 41 4e 53 5f 52 45 41 44 20 20 31 0a 23 64 65  RANS_READ  1.#de
40c0: 66 69 6e 65 20 54 52 41 4e 53 5f 57 52 49 54 45  fine TRANS_WRITE
40d0: 20 32 0a 0a 2f 2a 0a 2a 2a 20 41 6e 20 69 6e 73   2../*.** An ins
40e0: 74 61 6e 63 65 20 6f 66 20 74 68 69 73 20 6f 62  tance of this ob
40f0: 6a 65 63 74 20 72 65 70 72 65 73 65 6e 74 73 20  ject represents 
4100: 61 20 73 69 6e 67 6c 65 20 64 61 74 61 62 61 73  a single databas
4110: 65 20 66 69 6c 65 2e 0a 2a 2a 20 0a 2a 2a 20 41  e file..** .** A
4120: 20 73 69 6e 67 6c 65 20 64 61 74 61 62 61 73 65   single database
4130: 20 66 69 6c 65 20 63 61 6e 20 62 65 20 69 6e 20   file can be in 
4140: 75 73 65 20 61 73 20 74 68 65 20 73 61 6d 65 20  use as the same 
4150: 74 69 6d 65 20 62 79 20 74 77 6f 0a 2a 2a 20 6f  time by two.** o
4160: 72 20 6d 6f 72 65 20 64 61 74 61 62 61 73 65 20  r more database 
4170: 63 6f 6e 6e 65 63 74 69 6f 6e 73 2e 20 20 57 68  connections.  Wh
4180: 65 6e 20 74 77 6f 20 6f 72 20 6d 6f 72 65 20 63  en two or more c
4190: 6f 6e 6e 65 63 74 69 6f 6e 73 20 61 72 65 0a 2a  onnections are.*
41a0: 2a 20 73 68 61 72 69 6e 67 20 74 68 65 20 73 61  * sharing the sa
41b0: 6d 65 20 64 61 74 61 62 61 73 65 20 66 69 6c 65  me database file
41c0: 2c 20 65 61 63 68 20 63 6f 6e 6e 65 63 74 69 6f  , each connectio
41d0: 6e 20 68 61 73 20 69 74 20 6f 77 6e 0a 2a 2a 20  n has it own.** 
41e0: 70 72 69 76 61 74 65 20 42 74 72 65 65 20 6f 62  private Btree ob
41f0: 6a 65 63 74 20 66 6f 72 20 74 68 65 20 66 69 6c  ject for the fil
4200: 65 20 61 6e 64 20 65 61 63 68 20 6f 66 20 74 68  e and each of th
4210: 6f 73 65 20 42 74 72 65 65 73 20 70 6f 69 6e 74  ose Btrees point
4220: 73 0a 2a 2a 20 74 6f 20 74 68 69 73 20 6f 6e 65  s.** to this one
4230: 20 42 74 53 68 61 72 65 64 20 6f 62 6a 65 63 74   BtShared object
4240: 2e 20 20 42 74 53 68 61 72 65 64 2e 6e 52 65 66  .  BtShared.nRef
4250: 20 69 73 20 74 68 65 20 6e 75 6d 62 65 72 20 6f   is the number o
4260: 66 0a 2a 2a 20 63 6f 6e 6e 65 63 74 69 6f 6e 73  f.** connections
4270: 20 63 75 72 72 65 6e 74 6c 79 20 73 68 61 72 69   currently shari
4280: 6e 67 20 74 68 69 73 20 64 61 74 61 62 61 73 65  ng this database
4290: 20 66 69 6c 65 2e 0a 2a 2a 0a 2a 2a 20 46 69 65   file..**.** Fie
42a0: 6c 64 73 20 69 6e 20 74 68 69 73 20 73 74 72 75  lds in this stru
42b0: 63 74 75 72 65 20 61 72 65 20 61 63 63 65 73 73  cture are access
42c0: 65 64 20 75 6e 64 65 72 20 74 68 65 20 42 74 53  ed under the BtS
42d0: 68 61 72 65 64 2e 6d 75 74 65 78 0a 2a 2a 20 6d  hared.mutex.** m
42e0: 75 74 65 78 2c 20 65 78 63 65 70 74 20 66 6f 72  utex, except for
42f0: 20 6e 52 65 66 20 61 6e 64 20 70 4e 65 78 74 20   nRef and pNext 
4300: 77 68 69 63 68 20 61 72 65 20 61 63 63 65 73 73  which are access
4310: 65 64 20 75 6e 64 65 72 20 74 68 65 0a 2a 2a 20  ed under the.** 
4320: 67 6c 6f 62 61 6c 20 53 51 4c 49 54 45 5f 4d 55  global SQLITE_MU
4330: 54 45 58 5f 53 54 41 54 49 43 5f 4d 41 53 54 45  TEX_STATIC_MASTE
4340: 52 20 6d 75 74 65 78 2e 20 20 54 68 65 20 70 50  R mutex.  The pP
4350: 61 67 65 72 20 66 69 65 6c 64 0a 2a 2a 20 6d 61  ager field.** ma
4360: 79 20 6e 6f 74 20 62 65 20 6d 6f 64 69 66 69 65  y not be modifie
4370: 64 20 6f 6e 63 65 20 69 74 20 69 73 20 69 6e 69  d once it is ini
4380: 74 69 61 6c 6c 79 20 73 65 74 20 61 73 20 6c 6f  tially set as lo
4390: 6e 67 20 61 73 20 6e 52 65 66 3e 30 2e 0a 2a 2a  ng as nRef>0..**
43a0: 20 54 68 65 20 70 53 63 68 65 6d 61 20 66 69 65   The pSchema fie
43b0: 6c 64 20 6d 61 79 20 62 65 20 73 65 74 20 6f 6e  ld may be set on
43c0: 63 65 20 75 6e 64 65 72 20 42 74 53 68 61 72 65  ce under BtShare
43d0: 64 2e 6d 75 74 65 78 20 61 6e 64 0a 2a 2a 20 74  d.mutex and.** t
43e0: 68 65 72 65 61 66 74 65 72 20 69 73 20 75 6e 63  hereafter is unc
43f0: 68 61 6e 67 65 64 20 61 73 20 6c 6f 6e 67 20 61  hanged as long a
4400: 73 20 6e 52 65 66 3e 30 2e 0a 2a 2a 0a 2a 2a 20  s nRef>0..**.** 
4410: 69 73 50 65 6e 64 69 6e 67 3a 0a 2a 2a 0a 2a 2a  isPending:.**.**
4420: 20 20 20 49 66 20 61 20 42 74 53 68 61 72 65 64     If a BtShared
4430: 20 63 6c 69 65 6e 74 20 66 61 69 6c 73 20 74 6f   client fails to
4440: 20 6f 62 74 61 69 6e 20 61 20 77 72 69 74 65 2d   obtain a write-
4450: 6c 6f 63 6b 20 6f 6e 20 61 20 64 61 74 61 62 61  lock on a databa
4460: 73 65 0a 2a 2a 20 20 20 74 61 62 6c 65 20 28 62  se.**   table (b
4470: 65 63 61 75 73 65 20 74 68 65 72 65 20 65 78 69  ecause there exi
4480: 73 74 73 20 6f 6e 65 20 6f 72 20 6d 6f 72 65 20  sts one or more 
4490: 72 65 61 64 2d 6c 6f 63 6b 73 20 6f 6e 20 74 68  read-locks on th
44a0: 65 20 74 61 62 6c 65 29 2c 0a 2a 2a 20 20 20 74  e table),.**   t
44b0: 68 65 20 73 68 61 72 65 64 2d 63 61 63 68 65 20  he shared-cache 
44c0: 65 6e 74 65 72 73 20 27 70 65 6e 64 69 6e 67 2d  enters 'pending-
44d0: 6c 6f 63 6b 27 20 73 74 61 74 65 20 61 6e 64 20  lock' state and 
44e0: 69 73 50 65 6e 64 69 6e 67 20 69 73 0a 2a 2a 20  isPending is.** 
44f0: 20 20 73 65 74 20 74 6f 20 74 72 75 65 2e 0a 2a    set to true..*
4500: 2a 0a 2a 2a 20 20 20 54 68 65 20 73 68 61 72 65  *.**   The share
4510: 64 2d 63 61 63 68 65 20 6c 65 61 76 65 73 20 74  d-cache leaves t
4520: 68 65 20 27 70 65 6e 64 69 6e 67 20 6c 6f 63 6b  he 'pending lock
4530: 27 20 73 74 61 74 65 20 77 68 65 6e 20 65 69 74  ' state when eit
4540: 68 65 72 20 6f 66 0a 2a 2a 20 20 20 74 68 65 20  her of.**   the 
4550: 66 6f 6c 6c 6f 77 69 6e 67 20 6f 63 63 75 72 3a  following occur:
4560: 0a 2a 2a 0a 2a 2a 20 20 20 20 20 31 29 20 54 68  .**.**     1) Th
4570: 65 20 63 75 72 72 65 6e 74 20 77 72 69 74 65 72  e current writer
4580: 20 28 42 74 53 68 61 72 65 64 2e 70 57 72 69 74   (BtShared.pWrit
4590: 65 72 29 20 63 6f 6e 63 6c 75 64 65 73 20 69 74  er) concludes it
45a0: 73 20 74 72 61 6e 73 61 63 74 69 6f 6e 2c 20 4f  s transaction, O
45b0: 52 0a 2a 2a 20 20 20 20 20 32 29 20 54 68 65 20  R.**     2) The 
45c0: 6e 75 6d 62 65 72 20 6f 66 20 6c 6f 63 6b 73 20  number of locks 
45d0: 68 65 6c 64 20 62 79 20 6f 74 68 65 72 20 63 6f  held by other co
45e0: 6e 6e 65 63 74 69 6f 6e 73 20 64 72 6f 70 73 20  nnections drops 
45f0: 74 6f 20 7a 65 72 6f 2e 0a 2a 2a 0a 2a 2a 20 20  to zero..**.**  
4600: 20 77 68 69 6c 65 20 69 6e 20 74 68 65 20 27 70   while in the 'p
4610: 65 6e 64 69 6e 67 2d 6c 6f 63 6b 27 20 73 74 61  ending-lock' sta
4620: 74 65 2c 20 6e 6f 20 63 6f 6e 6e 65 63 74 69 6f  te, no connectio
4630: 6e 20 6d 61 79 20 73 74 61 72 74 20 61 20 6e 65  n may start a ne
4640: 77 0a 2a 2a 20 20 20 74 72 61 6e 73 61 63 74 69  w.**   transacti
4650: 6f 6e 2e 0a 2a 2a 0a 2a 2a 20 20 20 54 68 69 73  on..**.**   This
4660: 20 66 65 61 74 75 72 65 20 69 73 20 69 6e 63 6c   feature is incl
4670: 75 64 65 64 20 74 6f 20 68 65 6c 70 20 70 72 65  uded to help pre
4680: 76 65 6e 74 20 77 72 69 74 65 72 2d 73 74 61 72  vent writer-star
4690: 76 61 74 69 6f 6e 2e 0a 2a 2f 0a 73 74 72 75 63  vation..*/.struc
46a0: 74 20 42 74 53 68 61 72 65 64 20 7b 0a 20 20 50  t BtShared {.  P
46b0: 61 67 65 72 20 2a 70 50 61 67 65 72 3b 20 20 20  ager *pPager;   
46c0: 20 20 20 20 20 2f 2a 20 54 68 65 20 70 61 67 65       /* The page
46d0: 20 63 61 63 68 65 20 2a 2f 0a 20 20 73 71 6c 69   cache */.  sqli
46e0: 74 65 33 20 2a 64 62 3b 20 20 20 20 20 20 20 20  te3 *db;        
46f0: 20 20 2f 2a 20 44 61 74 61 62 61 73 65 20 63 6f    /* Database co
4700: 6e 6e 65 63 74 69 6f 6e 20 63 75 72 72 65 6e 74  nnection current
4710: 6c 79 20 75 73 69 6e 67 20 74 68 69 73 20 42 74  ly using this Bt
4720: 72 65 65 20 2a 2f 0a 20 20 42 74 43 75 72 73 6f  ree */.  BtCurso
4730: 72 20 2a 70 43 75 72 73 6f 72 3b 20 20 20 20 2f  r *pCursor;    /
4740: 2a 20 41 20 6c 69 73 74 20 6f 66 20 61 6c 6c 20  * A list of all 
4750: 6f 70 65 6e 20 63 75 72 73 6f 72 73 20 2a 2f 0a  open cursors */.
4760: 20 20 4d 65 6d 50 61 67 65 20 2a 70 50 61 67 65    MemPage *pPage
4770: 31 3b 20 20 20 20 20 20 2f 2a 20 46 69 72 73 74  1;      /* First
4780: 20 70 61 67 65 20 6f 66 20 74 68 65 20 64 61 74   page of the dat
4790: 61 62 61 73 65 20 2a 2f 0a 20 20 75 38 20 72 65  abase */.  u8 re
47a0: 61 64 4f 6e 6c 79 3b 20 20 20 20 20 20 20 20 20  adOnly;         
47b0: 20 2f 2a 20 54 72 75 65 20 69 66 20 74 68 65 20   /* True if the 
47c0: 75 6e 64 65 72 6c 79 69 6e 67 20 66 69 6c 65 20  underlying file 
47d0: 69 73 20 72 65 61 64 6f 6e 6c 79 20 2a 2f 0a 20  is readonly */. 
47e0: 20 75 38 20 70 61 67 65 53 69 7a 65 46 69 78 65   u8 pageSizeFixe
47f0: 64 3b 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69  d;     /* True i
4800: 66 20 74 68 65 20 70 61 67 65 20 73 69 7a 65 20  f the page size 
4810: 63 61 6e 20 6e 6f 20 6c 6f 6e 67 65 72 20 62 65  can no longer be
4820: 20 63 68 61 6e 67 65 64 20 2a 2f 0a 23 69 66 6e   changed */.#ifn
4830: 64 65 66 20 53 51 4c 49 54 45 5f 4f 4d 49 54 5f  def SQLITE_OMIT_
4840: 41 55 54 4f 56 41 43 55 55 4d 0a 20 20 75 38 20  AUTOVACUUM.  u8 
4850: 61 75 74 6f 56 61 63 75 75 6d 3b 20 20 20 20 20  autoVacuum;     
4860: 20 20 20 2f 2a 20 54 72 75 65 20 69 66 20 61 75     /* True if au
4870: 74 6f 2d 76 61 63 75 75 6d 20 69 73 20 65 6e 61  to-vacuum is ena
4880: 62 6c 65 64 20 2a 2f 0a 20 20 75 38 20 69 6e 63  bled */.  u8 inc
4890: 72 56 61 63 75 75 6d 3b 20 20 20 20 20 20 20 20  rVacuum;        
48a0: 2f 2a 20 54 72 75 65 20 69 66 20 69 6e 63 72 2d  /* True if incr-
48b0: 76 61 63 75 75 6d 20 69 73 20 65 6e 61 62 6c 65  vacuum is enable
48c0: 64 20 2a 2f 0a 23 65 6e 64 69 66 0a 20 20 75 31  d */.#endif.  u1
48d0: 36 20 70 61 67 65 53 69 7a 65 3b 20 20 20 20 20  6 pageSize;     
48e0: 20 20 20 20 2f 2a 20 54 6f 74 61 6c 20 6e 75 6d      /* Total num
48f0: 62 65 72 20 6f 66 20 62 79 74 65 73 20 6f 6e 20  ber of bytes on 
4900: 61 20 70 61 67 65 20 2a 2f 0a 20 20 75 31 36 20  a page */.  u16 
4910: 75 73 61 62 6c 65 53 69 7a 65 3b 20 20 20 20 20  usableSize;     
4920: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 75    /* Number of u
4930: 73 61 62 6c 65 20 62 79 74 65 73 20 6f 6e 20 65  sable bytes on e
4940: 61 63 68 20 70 61 67 65 20 2a 2f 0a 20 20 75 31  ach page */.  u1
4950: 36 20 6d 61 78 4c 6f 63 61 6c 3b 20 20 20 20 20  6 maxLocal;     
4960: 20 20 20 20 2f 2a 20 4d 61 78 69 6d 75 6d 20 6c      /* Maximum l
4970: 6f 63 61 6c 20 70 61 79 6c 6f 61 64 20 69 6e 20  ocal payload in 
4980: 6e 6f 6e 2d 4c 45 41 46 44 41 54 41 20 74 61 62  non-LEAFDATA tab
4990: 6c 65 73 20 2a 2f 0a 20 20 75 31 36 20 6d 69 6e  les */.  u16 min
49a0: 4c 6f 63 61 6c 3b 20 20 20 20 20 20 20 20 20 2f  Local;         /
49b0: 2a 20 4d 69 6e 69 6d 75 6d 20 6c 6f 63 61 6c 20  * Minimum local 
49c0: 70 61 79 6c 6f 61 64 20 69 6e 20 6e 6f 6e 2d 4c  payload in non-L
49d0: 45 41 46 44 41 54 41 20 74 61 62 6c 65 73 20 2a  EAFDATA tables *
49e0: 2f 0a 20 20 75 31 36 20 6d 61 78 4c 65 61 66 3b  /.  u16 maxLeaf;
49f0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4d 61 78            /* Max
4a00: 69 6d 75 6d 20 6c 6f 63 61 6c 20 70 61 79 6c 6f  imum local paylo
4a10: 61 64 20 69 6e 20 61 20 4c 45 41 46 44 41 54 41  ad in a LEAFDATA
4a20: 20 74 61 62 6c 65 20 2a 2f 0a 20 20 75 31 36 20   table */.  u16 
4a30: 6d 69 6e 4c 65 61 66 3b 20 20 20 20 20 20 20 20  minLeaf;        
4a40: 20 20 2f 2a 20 4d 69 6e 69 6d 75 6d 20 6c 6f 63    /* Minimum loc
4a50: 61 6c 20 70 61 79 6c 6f 61 64 20 69 6e 20 61 20  al payload in a 
4a60: 4c 45 41 46 44 41 54 41 20 74 61 62 6c 65 20 2a  LEAFDATA table *
4a70: 2f 0a 20 20 75 38 20 69 6e 54 72 61 6e 73 61 63  /.  u8 inTransac
4a80: 74 69 6f 6e 3b 20 20 20 20 20 2f 2a 20 54 72 61  tion;     /* Tra
4a90: 6e 73 61 63 74 69 6f 6e 20 73 74 61 74 65 20 2a  nsaction state *
4aa0: 2f 0a 20 20 69 6e 74 20 6e 54 72 61 6e 73 61 63  /.  int nTransac
4ab0: 74 69 6f 6e 3b 20 20 20 20 20 2f 2a 20 4e 75 6d  tion;     /* Num
4ac0: 62 65 72 20 6f 66 20 6f 70 65 6e 20 74 72 61 6e  ber of open tran
4ad0: 73 61 63 74 69 6f 6e 73 20 28 72 65 61 64 20 2b  sactions (read +
4ae0: 20 77 72 69 74 65 29 20 2a 2f 0a 20 20 76 6f 69   write) */.  voi
4af0: 64 20 2a 70 53 63 68 65 6d 61 3b 20 20 20 20 20  d *pSchema;     
4b00: 20 20 20 2f 2a 20 50 6f 69 6e 74 65 72 20 74 6f     /* Pointer to
4b10: 20 73 70 61 63 65 20 61 6c 6c 6f 63 61 74 65 64   space allocated
4b20: 20 62 79 20 73 71 6c 69 74 65 33 42 74 72 65 65   by sqlite3Btree
4b30: 53 63 68 65 6d 61 28 29 20 2a 2f 0a 20 20 76 6f  Schema() */.  vo
4b40: 69 64 20 28 2a 78 46 72 65 65 53 63 68 65 6d 61  id (*xFreeSchema
4b50: 29 28 76 6f 69 64 2a 29 3b 20 20 2f 2a 20 44 65  )(void*);  /* De
4b60: 73 74 72 75 63 74 6f 72 20 66 6f 72 20 42 74 53  structor for BtS
4b70: 68 61 72 65 64 2e 70 53 63 68 65 6d 61 20 2a 2f  hared.pSchema */
4b80: 0a 20 20 73 71 6c 69 74 65 33 5f 6d 75 74 65 78  .  sqlite3_mutex
4b90: 20 2a 6d 75 74 65 78 3b 20 2f 2a 20 4e 6f 6e 2d   *mutex; /* Non-
4ba0: 72 65 63 75 72 73 69 76 65 20 6d 75 74 65 78 20  recursive mutex 
4bb0: 72 65 71 75 69 72 65 64 20 74 6f 20 61 63 63 65  required to acce
4bc0: 73 73 20 74 68 69 73 20 73 74 72 75 63 74 20 2a  ss this struct *
4bd0: 2f 0a 20 20 42 69 74 76 65 63 20 2a 70 48 61 73  /.  Bitvec *pHas
4be0: 43 6f 6e 74 65 6e 74 3b 20 20 2f 2a 20 53 65 74  Content;  /* Set
4bf0: 20 6f 66 20 70 61 67 65 73 20 6d 6f 76 65 64 20   of pages moved 
4c00: 74 6f 20 66 72 65 65 2d 6c 69 73 74 20 74 68 69  to free-list thi
4c10: 73 20 74 72 61 6e 73 61 63 74 69 6f 6e 20 2a 2f  s transaction */
4c20: 0a 23 69 66 6e 64 65 66 20 53 51 4c 49 54 45 5f  .#ifndef SQLITE_
4c30: 4f 4d 49 54 5f 53 48 41 52 45 44 5f 43 41 43 48  OMIT_SHARED_CACH
4c40: 45 0a 20 20 69 6e 74 20 6e 52 65 66 3b 20 20 20  E.  int nRef;   
4c50: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d            /* Num
4c60: 62 65 72 20 6f 66 20 72 65 66 65 72 65 6e 63 65  ber of reference
4c70: 73 20 74 6f 20 74 68 69 73 20 73 74 72 75 63 74  s to this struct
4c80: 75 72 65 20 2a 2f 0a 20 20 42 74 53 68 61 72 65  ure */.  BtShare
4c90: 64 20 2a 70 4e 65 78 74 3b 20 20 20 20 20 20 2f  d *pNext;      /
4ca0: 2a 20 4e 65 78 74 20 6f 6e 20 61 20 6c 69 73 74  * Next on a list
4cb0: 20 6f 66 20 73 68 61 72 61 62 6c 65 20 42 74 53   of sharable BtS
4cc0: 68 61 72 65 64 20 73 74 72 75 63 74 73 20 2a 2f  hared structs */
4cd0: 0a 20 20 42 74 4c 6f 63 6b 20 2a 70 4c 6f 63 6b  .  BtLock *pLock
4ce0: 3b 20 20 20 20 20 20 20 20 2f 2a 20 4c 69 73 74  ;        /* List
4cf0: 20 6f 66 20 6c 6f 63 6b 73 20 68 65 6c 64 20 6f   of locks held o
4d00: 6e 20 74 68 69 73 20 73 68 61 72 65 64 2d 62 74  n this shared-bt
4d10: 72 65 65 20 73 74 72 75 63 74 20 2a 2f 0a 20 20  ree struct */.  
4d20: 42 74 72 65 65 20 2a 70 57 72 69 74 65 72 3b 20  Btree *pWriter; 
4d30: 20 20 20 20 20 20 2f 2a 20 42 74 72 65 65 20 77        /* Btree w
4d40: 69 74 68 20 63 75 72 72 65 6e 74 6c 79 20 6f 70  ith currently op
4d50: 65 6e 20 77 72 69 74 65 20 74 72 61 6e 73 61 63  en write transac
4d60: 74 69 6f 6e 20 2a 2f 0a 20 20 75 38 20 69 73 45  tion */.  u8 isE
4d70: 78 63 6c 75 73 69 76 65 3b 20 20 20 20 20 20 20  xclusive;       
4d80: 2f 2a 20 54 72 75 65 20 69 66 20 70 57 72 69 74  /* True if pWrit
4d90: 65 72 20 68 61 73 20 61 6e 20 45 58 43 4c 55 53  er has an EXCLUS
4da0: 49 56 45 20 6c 6f 63 6b 20 6f 6e 20 74 68 65 20  IVE lock on the 
4db0: 64 62 20 2a 2f 0a 20 20 75 38 20 69 73 50 65 6e  db */.  u8 isPen
4dc0: 64 69 6e 67 3b 20 20 20 20 20 20 20 20 20 2f 2a  ding;         /*
4dd0: 20 49 66 20 77 61 69 74 69 6e 67 20 66 6f 72 20   If waiting for 
4de0: 72 65 61 64 2d 6c 6f 63 6b 73 20 74 6f 20 63 6c  read-locks to cl
4df0: 65 61 72 20 2a 2f 0a 23 65 6e 64 69 66 0a 20 20  ear */.#endif.  
4e00: 75 38 20 2a 70 54 6d 70 53 70 61 63 65 3b 20 20  u8 *pTmpSpace;  
4e10: 20 20 20 20 20 20 2f 2a 20 42 74 53 68 61 72 65        /* BtShare
4e20: 64 2e 70 61 67 65 53 69 7a 65 20 62 79 74 65 73  d.pageSize bytes
4e30: 20 6f 66 20 73 70 61 63 65 20 66 6f 72 20 74 6d   of space for tm
4e40: 70 20 75 73 65 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a  p use */.};../*.
4e50: 2a 2a 20 41 6e 20 69 6e 73 74 61 6e 63 65 20 6f  ** An instance o
4e60: 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20  f the following 
4e70: 73 74 72 75 63 74 75 72 65 20 69 73 20 75 73 65  structure is use
4e80: 64 20 74 6f 20 68 6f 6c 64 20 69 6e 66 6f 72 6d  d to hold inform
4e90: 61 74 69 6f 6e 0a 2a 2a 20 61 62 6f 75 74 20 61  ation.** about a
4ea0: 20 63 65 6c 6c 2e 20 20 54 68 65 20 70 61 72 73   cell.  The pars
4eb0: 65 43 65 6c 6c 50 74 72 28 29 20 66 75 6e 63 74  eCellPtr() funct
4ec0: 69 6f 6e 20 66 69 6c 6c 73 20 69 6e 20 74 68 69  ion fills in thi
4ed0: 73 20 73 74 72 75 63 74 75 72 65 0a 2a 2a 20 62  s structure.** b
4ee0: 61 73 65 64 20 6f 6e 20 69 6e 66 6f 72 6d 61 74  ased on informat
4ef0: 69 6f 6e 20 65 78 74 72 61 63 74 20 66 72 6f 6d  ion extract from
4f00: 20 74 68 65 20 72 61 77 20 64 69 73 6b 20 70 61   the raw disk pa
4f10: 67 65 2e 0a 2a 2f 0a 74 79 70 65 64 65 66 20 73  ge..*/.typedef s
4f20: 74 72 75 63 74 20 43 65 6c 6c 49 6e 66 6f 20 43  truct CellInfo C
4f30: 65 6c 6c 49 6e 66 6f 3b 0a 73 74 72 75 63 74 20  ellInfo;.struct 
4f40: 43 65 6c 6c 49 6e 66 6f 20 7b 0a 20 20 75 38 20  CellInfo {.  u8 
4f50: 2a 70 43 65 6c 6c 3b 20 20 20 20 20 2f 2a 20 50  *pCell;     /* P
4f60: 6f 69 6e 74 65 72 20 74 6f 20 74 68 65 20 73 74  ointer to the st
4f70: 61 72 74 20 6f 66 20 63 65 6c 6c 20 63 6f 6e 74  art of cell cont
4f80: 65 6e 74 20 2a 2f 0a 20 20 69 36 34 20 6e 4b 65  ent */.  i64 nKe
4f90: 79 3b 20 20 20 20 20 20 2f 2a 20 54 68 65 20 6b  y;      /* The k
4fa0: 65 79 20 66 6f 72 20 49 4e 54 4b 45 59 20 74 61  ey for INTKEY ta
4fb0: 62 6c 65 73 2c 20 6f 72 20 6e 75 6d 62 65 72 20  bles, or number 
4fc0: 6f 66 20 62 79 74 65 73 20 69 6e 20 6b 65 79 20  of bytes in key 
4fd0: 2a 2f 0a 20 20 75 33 32 20 6e 44 61 74 61 3b 20  */.  u32 nData; 
4fe0: 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66      /* Number of
4ff0: 20 62 79 74 65 73 20 6f 66 20 64 61 74 61 20 2a   bytes of data *
5000: 2f 0a 20 20 75 33 32 20 6e 50 61 79 6c 6f 61 64  /.  u32 nPayload
5010: 3b 20 20 2f 2a 20 54 6f 74 61 6c 20 61 6d 6f 75  ;  /* Total amou
5020: 6e 74 20 6f 66 20 70 61 79 6c 6f 61 64 20 2a 2f  nt of payload */
5030: 0a 20 20 75 31 36 20 6e 48 65 61 64 65 72 3b 20  .  u16 nHeader; 
5040: 20 20 2f 2a 20 53 69 7a 65 20 6f 66 20 74 68 65    /* Size of the
5050: 20 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 20 68 65   cell content he
5060: 61 64 65 72 20 69 6e 20 62 79 74 65 73 20 2a 2f  ader in bytes */
5070: 0a 20 20 75 31 36 20 6e 4c 6f 63 61 6c 3b 20 20  .  u16 nLocal;  
5080: 20 20 2f 2a 20 41 6d 6f 75 6e 74 20 6f 66 20 70    /* Amount of p
5090: 61 79 6c 6f 61 64 20 68 65 6c 64 20 6c 6f 63 61  ayload held loca
50a0: 6c 6c 79 20 2a 2f 0a 20 20 75 31 36 20 69 4f 76  lly */.  u16 iOv
50b0: 65 72 66 6c 6f 77 3b 20 2f 2a 20 4f 66 66 73 65  erflow; /* Offse
50c0: 74 20 74 6f 20 6f 76 65 72 66 6c 6f 77 20 70 61  t to overflow pa
50d0: 67 65 20 6e 75 6d 62 65 72 2e 20 20 5a 65 72 6f  ge number.  Zero
50e0: 20 69 66 20 6e 6f 20 6f 76 65 72 66 6c 6f 77 20   if no overflow 
50f0: 2a 2f 0a 20 20 75 31 36 20 6e 53 69 7a 65 3b 20  */.  u16 nSize; 
5100: 20 20 20 20 2f 2a 20 53 69 7a 65 20 6f 66 20 74      /* Size of t
5110: 68 65 20 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 20  he cell content 
5120: 6f 6e 20 74 68 65 20 6d 61 69 6e 20 62 2d 74 72  on the main b-tr
5130: 65 65 20 70 61 67 65 20 2a 2f 0a 7d 3b 0a 0a 2f  ee page */.};../
5140: 2a 0a 2a 2a 20 4d 61 78 69 6d 75 6d 20 64 65 70  *.** Maximum dep
5150: 74 68 20 6f 66 20 61 6e 20 53 51 4c 69 74 65 20  th of an SQLite 
5160: 42 2d 54 72 65 65 20 73 74 72 75 63 74 75 72 65  B-Tree structure
5170: 2e 20 41 6e 79 20 42 2d 54 72 65 65 20 64 65 65  . Any B-Tree dee
5180: 70 65 72 20 74 68 61 6e 0a 2a 2a 20 74 68 69 73  per than.** this
5190: 20 77 69 6c 6c 20 62 65 20 64 65 63 6c 61 72 65   will be declare
51a0: 64 20 63 6f 72 72 75 70 74 2e 20 54 68 69 73 20  d corrupt. This 
51b0: 76 61 6c 75 65 20 69 73 20 63 61 6c 63 75 6c 61  value is calcula
51c0: 74 65 64 20 62 61 73 65 64 20 6f 6e 20 61 0a 2a  ted based on a.*
51d0: 2a 20 6d 61 78 69 6d 75 6d 20 64 61 74 61 62 61  * maximum databa
51e0: 73 65 20 73 69 7a 65 20 6f 66 20 32 5e 33 31 20  se size of 2^31 
51f0: 70 61 67 65 73 20 61 20 6d 69 6e 69 6d 75 6d 20  pages a minimum 
5200: 66 61 6e 6f 75 74 20 6f 66 20 32 20 66 6f 72 20  fanout of 2 for 
5210: 61 0a 2a 2a 20 72 6f 6f 74 2d 6e 6f 64 65 20 61  a.** root-node a
5220: 6e 64 20 33 20 66 6f 72 20 61 6c 6c 20 6f 74 68  nd 3 for all oth
5230: 65 72 20 69 6e 74 65 72 6e 61 6c 20 6e 6f 64 65  er internal node
5240: 73 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 61 20 74 72  s..**.** If a tr
5250: 65 65 20 74 68 61 74 20 61 70 70 65 61 72 73 20  ee that appears 
5260: 74 6f 20 62 65 20 74 61 6c 6c 65 72 20 74 68 61  to be taller tha
5270: 6e 20 74 68 69 73 20 69 73 20 65 6e 63 6f 75 6e  n this is encoun
5280: 74 65 72 65 64 2c 20 69 74 20 69 73 0a 2a 2a 20  tered, it is.** 
5290: 61 73 73 75 6d 65 64 20 74 68 61 74 20 74 68 65  assumed that the
52a0: 20 64 61 74 61 62 61 73 65 20 69 73 20 63 6f 72   database is cor
52b0: 72 75 70 74 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65  rupt..*/.#define
52c0: 20 42 54 43 55 52 53 4f 52 5f 4d 41 58 5f 44 45   BTCURSOR_MAX_DE
52d0: 50 54 48 20 32 30 0a 0a 2f 2a 0a 2a 2a 20 41 20  PTH 20../*.** A 
52e0: 63 75 72 73 6f 72 20 69 73 20 61 20 70 6f 69 6e  cursor is a poin
52f0: 74 65 72 20 74 6f 20 61 20 70 61 72 74 69 63 75  ter to a particu
5300: 6c 61 72 20 65 6e 74 72 79 20 77 69 74 68 69 6e  lar entry within
5310: 20 61 20 70 61 72 74 69 63 75 6c 61 72 0a 2a 2a   a particular.**
5320: 20 62 2d 74 72 65 65 20 77 69 74 68 69 6e 20 61   b-tree within a
5330: 20 64 61 74 61 62 61 73 65 20 66 69 6c 65 2e 0a   database file..
5340: 2a 2a 0a 2a 2a 20 54 68 65 20 65 6e 74 72 79 20  **.** The entry 
5350: 69 73 20 69 64 65 6e 74 69 66 69 65 64 20 62 79  is identified by
5360: 20 69 74 73 20 4d 65 6d 50 61 67 65 20 61 6e 64   its MemPage and
5370: 20 74 68 65 20 69 6e 64 65 78 20 69 6e 0a 2a 2a   the index in.**
5380: 20 4d 65 6d 50 61 67 65 2e 61 43 65 6c 6c 5b 5d   MemPage.aCell[]
5390: 20 6f 66 20 74 68 65 20 65 6e 74 72 79 2e 0a 2a   of the entry..*
53a0: 2a 0a 2a 2a 20 41 20 73 69 6e 67 6c 65 20 64 61  *.** A single da
53b0: 74 61 62 61 73 65 20 66 69 6c 65 20 63 61 6e 20  tabase file can 
53c0: 73 68 61 72 65 64 20 62 79 20 74 77 6f 20 6d 6f  shared by two mo
53d0: 72 65 20 64 61 74 61 62 61 73 65 20 63 6f 6e 6e  re database conn
53e0: 65 63 74 69 6f 6e 73 2c 0a 2a 2a 20 62 75 74 20  ections,.** but 
53f0: 63 75 72 73 6f 72 73 20 63 61 6e 6e 6f 74 20 62  cursors cannot b
5400: 65 20 73 68 61 72 65 64 2e 20 20 45 61 63 68 20  e shared.  Each 
5410: 63 75 72 73 6f 72 20 69 73 20 61 73 73 6f 63 69  cursor is associ
5420: 61 74 65 64 20 77 69 74 68 20 61 0a 2a 2a 20 70  ated with a.** p
5430: 61 72 74 69 63 75 6c 61 72 20 64 61 74 61 62 61  articular databa
5440: 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 20 69 64  se connection id
5450: 65 6e 74 69 66 69 65 64 20 42 74 43 75 72 73 6f  entified BtCurso
5460: 72 2e 70 42 74 72 65 65 2e 64 62 2e 0a 2a 2a 0a  r.pBtree.db..**.
5470: 2a 2a 20 46 69 65 6c 64 73 20 69 6e 20 74 68 69  ** Fields in thi
5480: 73 20 73 74 72 75 63 74 75 72 65 20 61 72 65 20  s structure are 
5490: 61 63 63 65 73 73 65 64 20 75 6e 64 65 72 20 74  accessed under t
54a0: 68 65 20 42 74 53 68 61 72 65 64 2e 6d 75 74 65  he BtShared.mute
54b0: 78 0a 2a 2a 20 66 6f 75 6e 64 20 61 74 20 73 65  x.** found at se
54c0: 6c 66 2d 3e 70 42 74 2d 3e 6d 75 74 65 78 2e 20  lf->pBt->mutex. 
54d0: 0a 2a 2f 0a 73 74 72 75 63 74 20 42 74 43 75 72  .*/.struct BtCur
54e0: 73 6f 72 20 7b 0a 20 20 42 74 72 65 65 20 2a 70  sor {.  Btree *p
54f0: 42 74 72 65 65 3b 20 20 20 20 20 20 20 20 20 20  Btree;          
5500: 20 20 2f 2a 20 54 68 65 20 42 74 72 65 65 20 74    /* The Btree t
5510: 6f 20 77 68 69 63 68 20 74 68 69 73 20 63 75 72  o which this cur
5520: 73 6f 72 20 62 65 6c 6f 6e 67 73 20 2a 2f 0a 20  sor belongs */. 
5530: 20 42 74 53 68 61 72 65 64 20 2a 70 42 74 3b 20   BtShared *pBt; 
5540: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68             /* Th
5550: 65 20 42 74 53 68 61 72 65 64 20 74 68 69 73 20  e BtShared this 
5560: 63 75 72 73 6f 72 20 70 6f 69 6e 74 73 20 74 6f  cursor points to
5570: 20 2a 2f 0a 20 20 42 74 43 75 72 73 6f 72 20 2a   */.  BtCursor *
5580: 70 4e 65 78 74 2c 20 2a 70 50 72 65 76 3b 20 20  pNext, *pPrev;  
5590: 2f 2a 20 46 6f 72 6d 73 20 61 20 6c 69 6e 6b 65  /* Forms a linke
55a0: 64 20 6c 69 73 74 20 6f 66 20 61 6c 6c 20 63 75  d list of all cu
55b0: 72 73 6f 72 73 20 2a 2f 0a 20 20 73 74 72 75 63  rsors */.  struc
55c0: 74 20 4b 65 79 49 6e 66 6f 20 2a 70 4b 65 79 49  t KeyInfo *pKeyI
55d0: 6e 66 6f 3b 20 2f 2a 20 41 72 67 75 6d 65 6e 74  nfo; /* Argument
55e0: 20 70 61 73 73 65 64 20 74 6f 20 63 6f 6d 70 61   passed to compa
55f0: 72 69 73 6f 6e 20 66 75 6e 63 74 69 6f 6e 20 2a  rison function *
5600: 2f 0a 20 20 50 67 6e 6f 20 70 67 6e 6f 52 6f 6f  /.  Pgno pgnoRoo
5610: 74 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a  t;            /*
5620: 20 54 68 65 20 72 6f 6f 74 20 70 61 67 65 20 6f   The root page o
5630: 66 20 74 68 69 73 20 74 72 65 65 20 2a 2f 0a 20  f this tree */. 
5640: 20 73 71 6c 69 74 65 33 5f 69 6e 74 36 34 20 63   sqlite3_int64 c
5650: 61 63 68 65 64 52 6f 77 69 64 3b 20 2f 2a 20 4e  achedRowid; /* N
5660: 65 78 74 20 72 6f 77 69 64 20 63 61 63 68 65 2e  ext rowid cache.
5670: 20 20 30 20 6d 65 61 6e 73 20 6e 6f 74 20 76 61    0 means not va
5680: 6c 69 64 20 2a 2f 0a 20 20 43 65 6c 6c 49 6e 66  lid */.  CellInf
5690: 6f 20 69 6e 66 6f 3b 20 20 20 20 20 20 20 20 20  o info;         
56a0: 20 20 20 2f 2a 20 41 20 70 61 72 73 65 20 6f 66     /* A parse of
56b0: 20 74 68 65 20 63 65 6c 6c 20 77 65 20 61 72 65   the cell we are
56c0: 20 70 6f 69 6e 74 69 6e 67 20 61 74 20 2a 2f 0a   pointing at */.
56d0: 20 20 75 38 20 77 72 46 6c 61 67 3b 20 20 20 20    u8 wrFlag;    
56e0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54              /* T
56f0: 72 75 65 20 69 66 20 77 72 69 74 61 62 6c 65 20  rue if writable 
5700: 2a 2f 0a 20 20 75 38 20 61 74 4c 61 73 74 3b 20  */.  u8 atLast; 
5710: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f                 /
5720: 2a 20 43 75 72 73 6f 72 20 70 6f 69 6e 74 69 6e  * Cursor pointin
5730: 67 20 74 6f 20 74 68 65 20 6c 61 73 74 20 65 6e  g to the last en
5740: 74 72 79 20 2a 2f 0a 20 20 75 38 20 76 61 6c 69  try */.  u8 vali
5750: 64 4e 4b 65 79 3b 20 20 20 20 20 20 20 20 20 20  dNKey;          
5760: 20 20 20 2f 2a 20 54 72 75 65 20 69 66 20 69 6e     /* True if in
5770: 66 6f 2e 6e 4b 65 79 20 69 73 20 76 61 6c 69 64  fo.nKey is valid
5780: 20 2a 2f 0a 20 20 75 38 20 65 53 74 61 74 65 3b   */.  u8 eState;
5790: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
57a0: 2f 2a 20 4f 6e 65 20 6f 66 20 74 68 65 20 43 55  /* One of the CU
57b0: 52 53 4f 52 5f 58 58 58 20 63 6f 6e 73 74 61 6e  RSOR_XXX constan
57c0: 74 73 20 28 73 65 65 20 62 65 6c 6f 77 29 20 2a  ts (see below) *
57d0: 2f 0a 20 20 76 6f 69 64 20 2a 70 4b 65 79 3b 20  /.  void *pKey; 
57e0: 20 20 20 20 20 2f 2a 20 53 61 76 65 64 20 6b 65       /* Saved ke
57f0: 79 20 74 68 61 74 20 77 61 73 20 63 75 72 73 6f  y that was curso
5800: 72 27 73 20 6c 61 73 74 20 6b 6e 6f 77 6e 20 70  r's last known p
5810: 6f 73 69 74 69 6f 6e 20 2a 2f 0a 20 20 69 36 34  osition */.  i64
5820: 20 6e 4b 65 79 3b 20 20 20 20 20 20 20 20 2f 2a   nKey;        /*
5830: 20 53 69 7a 65 20 6f 66 20 70 4b 65 79 2c 20 6f   Size of pKey, o
5840: 72 20 6c 61 73 74 20 69 6e 74 65 67 65 72 20 6b  r last integer k
5850: 65 79 20 2a 2f 0a 20 20 69 6e 74 20 73 6b 69 70  ey */.  int skip
5860: 4e 65 78 74 3b 20 20 20 20 2f 2a 20 50 72 65 76  Next;    /* Prev
5870: 28 29 20 69 73 20 6e 6f 6f 70 20 69 66 20 6e 65  () is noop if ne
5880: 67 61 74 69 76 65 2e 20 4e 65 78 74 28 29 20 69  gative. Next() i
5890: 73 20 6e 6f 6f 70 20 69 66 20 70 6f 73 69 74 69  s noop if positi
58a0: 76 65 20 2a 2f 0a 23 69 66 6e 64 65 66 20 53 51  ve */.#ifndef SQ
58b0: 4c 49 54 45 5f 4f 4d 49 54 5f 49 4e 43 52 42 4c  LITE_OMIT_INCRBL
58c0: 4f 42 0a 20 20 75 38 20 69 73 49 6e 63 72 62 6c  OB.  u8 isIncrbl
58d0: 6f 62 48 61 6e 64 6c 65 3b 20 20 20 20 20 20 2f  obHandle;      /
58e0: 2a 20 54 72 75 65 20 69 66 20 74 68 69 73 20 63  * True if this c
58f0: 75 72 73 6f 72 20 69 73 20 61 6e 20 69 6e 63 72  ursor is an incr
5900: 2e 20 69 6f 20 68 61 6e 64 6c 65 20 2a 2f 0a 20  . io handle */. 
5910: 20 50 67 6e 6f 20 2a 61 4f 76 65 72 66 6c 6f 77   Pgno *aOverflow
5920: 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 43 61  ;          /* Ca
5930: 63 68 65 20 6f 66 20 6f 76 65 72 66 6c 6f 77 20  che of overflow 
5940: 70 61 67 65 20 6c 6f 63 61 74 69 6f 6e 73 20 2a  page locations *
5950: 2f 0a 23 65 6e 64 69 66 0a 20 20 69 31 36 20 69  /.#endif.  i16 i
5960: 50 61 67 65 3b 20 20 20 20 20 20 20 20 20 20 20  Page;           
5970: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
5980: 20 2f 2a 20 49 6e 64 65 78 20 6f 66 20 63 75 72   /* Index of cur
5990: 72 65 6e 74 20 70 61 67 65 20 69 6e 20 61 70 50  rent page in apP
59a0: 61 67 65 20 2a 2f 0a 20 20 4d 65 6d 50 61 67 65  age */.  MemPage
59b0: 20 2a 61 70 50 61 67 65 5b 42 54 43 55 52 53 4f   *apPage[BTCURSO
59c0: 52 5f 4d 41 58 5f 44 45 50 54 48 5d 3b 20 20 2f  R_MAX_DEPTH];  /
59d0: 2a 20 50 61 67 65 73 20 66 72 6f 6d 20 72 6f 6f  * Pages from roo
59e0: 74 20 74 6f 20 63 75 72 72 65 6e 74 20 70 61 67  t to current pag
59f0: 65 20 2a 2f 0a 20 20 75 31 36 20 61 69 49 64 78  e */.  u16 aiIdx
5a00: 5b 42 54 43 55 52 53 4f 52 5f 4d 41 58 5f 44 45  [BTCURSOR_MAX_DE
5a10: 50 54 48 5d 3b 20 20 20 20 20 20 20 20 2f 2a 20  PTH];        /* 
5a20: 43 75 72 72 65 6e 74 20 69 6e 64 65 78 20 69 6e  Current index in
5a30: 20 61 70 50 61 67 65 5b 69 5d 20 2a 2f 0a 7d 3b   apPage[i] */.};
5a40: 0a 0a 2f 2a 0a 2a 2a 20 50 6f 74 65 6e 74 69 61  ../*.** Potentia
5a50: 6c 20 76 61 6c 75 65 73 20 66 6f 72 20 42 74 43  l values for BtC
5a60: 75 72 73 6f 72 2e 65 53 74 61 74 65 2e 0a 2a 2a  ursor.eState..**
5a70: 0a 2a 2a 20 43 55 52 53 4f 52 5f 56 41 4c 49 44  .** CURSOR_VALID
5a80: 3a 0a 2a 2a 20 20 20 43 75 72 73 6f 72 20 70 6f  :.**   Cursor po
5a90: 69 6e 74 73 20 74 6f 20 61 20 76 61 6c 69 64 20  ints to a valid 
5aa0: 65 6e 74 72 79 2e 20 67 65 74 50 61 79 6c 6f 61  entry. getPayloa
5ab0: 64 28 29 20 65 74 63 2e 20 6d 61 79 20 62 65 20  d() etc. may be 
5ac0: 63 61 6c 6c 65 64 2e 0a 2a 2a 0a 2a 2a 20 43 55  called..**.** CU
5ad0: 52 53 4f 52 5f 49 4e 56 41 4c 49 44 3a 0a 2a 2a  RSOR_INVALID:.**
5ae0: 20 20 20 43 75 72 73 6f 72 20 64 6f 65 73 20 6e     Cursor does n
5af0: 6f 74 20 70 6f 69 6e 74 20 74 6f 20 61 20 76 61  ot point to a va
5b00: 6c 69 64 20 65 6e 74 72 79 2e 20 54 68 69 73 20  lid entry. This 
5b10: 63 61 6e 20 68 61 70 70 65 6e 20 28 66 6f 72 20  can happen (for 
5b20: 65 78 61 6d 70 6c 65 29 20 0a 2a 2a 20 20 20 62  example) .**   b
5b30: 65 63 61 75 73 65 20 74 68 65 20 74 61 62 6c 65  ecause the table
5b40: 20 69 73 20 65 6d 70 74 79 20 6f 72 20 62 65 63   is empty or bec
5b50: 61 75 73 65 20 42 74 72 65 65 43 75 72 73 6f 72  ause BtreeCursor
5b60: 46 69 72 73 74 28 29 20 68 61 73 20 6e 6f 74 20  First() has not 
5b70: 62 65 65 6e 0a 2a 2a 20 20 20 63 61 6c 6c 65 64  been.**   called
5b80: 2e 0a 2a 2a 0a 2a 2a 20 43 55 52 53 4f 52 5f 52  ..**.** CURSOR_R
5b90: 45 51 55 49 52 45 53 45 45 4b 3a 0a 2a 2a 20 20  EQUIRESEEK:.**  
5ba0: 20 54 68 65 20 74 61 62 6c 65 20 74 68 61 74 20   The table that 
5bb0: 74 68 69 73 20 63 75 72 73 6f 72 20 77 61 73 20  this cursor was 
5bc0: 6f 70 65 6e 65 64 20 6f 6e 20 73 74 69 6c 6c 20  opened on still 
5bd0: 65 78 69 73 74 73 2c 20 62 75 74 20 68 61 73 20  exists, but has 
5be0: 62 65 65 6e 20 0a 2a 2a 20 20 20 6d 6f 64 69 66  been .**   modif
5bf0: 69 65 64 20 73 69 6e 63 65 20 74 68 65 20 63 75  ied since the cu
5c00: 72 73 6f 72 20 77 61 73 20 6c 61 73 74 20 75 73  rsor was last us
5c10: 65 64 2e 20 54 68 65 20 63 75 72 73 6f 72 20 70  ed. The cursor p
5c20: 6f 73 69 74 69 6f 6e 20 69 73 20 73 61 76 65 64  osition is saved
5c30: 0a 2a 2a 20 20 20 69 6e 20 76 61 72 69 61 62 6c  .**   in variabl
5c40: 65 73 20 42 74 43 75 72 73 6f 72 2e 70 4b 65 79  es BtCursor.pKey
5c50: 20 61 6e 64 20 42 74 43 75 72 73 6f 72 2e 6e 4b   and BtCursor.nK
5c60: 65 79 2e 20 57 68 65 6e 20 61 20 63 75 72 73 6f  ey. When a curso
5c70: 72 20 69 73 20 69 6e 20 0a 2a 2a 20 20 20 74 68  r is in .**   th
5c80: 69 73 20 73 74 61 74 65 2c 20 72 65 73 74 6f 72  is state, restor
5c90: 65 43 75 72 73 6f 72 50 6f 73 69 74 69 6f 6e 28  eCursorPosition(
5ca0: 29 20 63 61 6e 20 62 65 20 63 61 6c 6c 65 64 20  ) can be called 
5cb0: 74 6f 20 61 74 74 65 6d 70 74 20 74 6f 0a 2a 2a  to attempt to.**
5cc0: 20 20 20 73 65 65 6b 20 74 68 65 20 63 75 72 73     seek the curs
5cd0: 6f 72 20 74 6f 20 74 68 65 20 73 61 76 65 64 20  or to the saved 
5ce0: 70 6f 73 69 74 69 6f 6e 2e 0a 2a 2a 0a 2a 2a 20  position..**.** 
5cf0: 43 55 52 53 4f 52 5f 46 41 55 4c 54 3a 0a 2a 2a  CURSOR_FAULT:.**
5d00: 20 20 20 41 20 75 6e 72 65 63 6f 76 65 72 61 62     A unrecoverab
5d10: 6c 65 20 65 72 72 6f 72 20 28 61 6e 20 49 2f 4f  le error (an I/O
5d20: 20 65 72 72 6f 72 20 6f 72 20 61 20 6d 61 6c 6c   error or a mall
5d30: 6f 63 20 66 61 69 6c 75 72 65 29 20 68 61 73 20  oc failure) has 
5d40: 6f 63 63 75 72 72 65 64 0a 2a 2a 20 20 20 6f 6e  occurred.**   on
5d50: 20 61 20 64 69 66 66 65 72 65 6e 74 20 63 6f 6e   a different con
5d60: 6e 65 63 74 69 6f 6e 20 74 68 61 74 20 73 68 61  nection that sha
5d70: 72 65 73 20 74 68 65 20 42 74 53 68 61 72 65 64  res the BtShared
5d80: 20 63 61 63 68 65 20 77 69 74 68 20 74 68 69 73   cache with this
5d90: 0a 2a 2a 20 20 20 63 75 72 73 6f 72 2e 20 20 54  .**   cursor.  T
5da0: 68 65 20 65 72 72 6f 72 20 68 61 73 20 6c 65 66  he error has lef
5db0: 74 20 74 68 65 20 63 61 63 68 65 20 69 6e 20 61  t the cache in a
5dc0: 6e 20 69 6e 63 6f 6e 73 69 73 74 65 6e 74 20 73  n inconsistent s
5dd0: 74 61 74 65 2e 0a 2a 2a 20 20 20 44 6f 20 6e 6f  tate..**   Do no
5de0: 74 68 69 6e 67 20 65 6c 73 65 20 77 69 74 68 20  thing else with 
5df0: 74 68 69 73 20 63 75 72 73 6f 72 2e 20 20 41 6e  this cursor.  An
5e00: 79 20 61 74 74 65 6d 70 74 20 74 6f 20 75 73 65  y attempt to use
5e10: 20 74 68 65 20 63 75 72 73 6f 72 0a 2a 2a 20 20   the cursor.**  
5e20: 20 73 68 6f 75 6c 64 20 72 65 74 75 72 6e 20 74   should return t
5e30: 68 65 20 65 72 72 6f 72 20 63 6f 64 65 20 73 74  he error code st
5e40: 6f 72 65 64 20 69 6e 20 42 74 43 75 72 73 6f 72  ored in BtCursor
5e50: 2e 73 6b 69 70 0a 2a 2f 0a 23 64 65 66 69 6e 65  .skip.*/.#define
5e60: 20 43 55 52 53 4f 52 5f 49 4e 56 41 4c 49 44 20   CURSOR_INVALID 
5e70: 20 20 20 20 20 20 20 20 20 20 30 0a 23 64 65 66            0.#def
5e80: 69 6e 65 20 43 55 52 53 4f 52 5f 56 41 4c 49 44  ine CURSOR_VALID
5e90: 20 20 20 20 20 20 20 20 20 20 20 20 20 31 0a 23               1.#
5ea0: 64 65 66 69 6e 65 20 43 55 52 53 4f 52 5f 52 45  define CURSOR_RE
5eb0: 51 55 49 52 45 53 45 45 4b 20 20 20 20 20 20 20  QUIRESEEK       
5ec0: 32 0a 23 64 65 66 69 6e 65 20 43 55 52 53 4f 52  2.#define CURSOR
5ed0: 5f 46 41 55 4c 54 20 20 20 20 20 20 20 20 20 20  _FAULT          
5ee0: 20 20 20 33 0a 0a 2f 2a 20 0a 2a 2a 20 54 68 65     3../* .** The
5ef0: 20 64 61 74 61 62 61 73 65 20 70 61 67 65 20 74   database page t
5f00: 68 65 20 50 45 4e 44 49 4e 47 5f 42 59 54 45 20  he PENDING_BYTE 
5f10: 6f 63 63 75 70 69 65 73 2e 20 54 68 69 73 20 70  occupies. This p
5f20: 61 67 65 20 69 73 20 6e 65 76 65 72 20 75 73 65  age is never use
5f30: 64 2e 0a 2a 2f 0a 23 20 64 65 66 69 6e 65 20 50  d..*/.# define P
5f40: 45 4e 44 49 4e 47 5f 42 59 54 45 5f 50 41 47 45  ENDING_BYTE_PAGE
5f50: 28 70 42 74 29 20 50 41 47 45 52 5f 4d 4a 5f 50  (pBt) PAGER_MJ_P
5f60: 47 4e 4f 28 70 42 74 29 0a 0a 2f 2a 0a 2a 2a 20  GNO(pBt)../*.** 
5f70: 54 68 65 73 65 20 6d 61 63 72 6f 73 20 64 65 66  These macros def
5f80: 69 6e 65 20 74 68 65 20 6c 6f 63 61 74 69 6f 6e  ine the location
5f90: 20 6f 66 20 74 68 65 20 70 6f 69 6e 74 65 72 2d   of the pointer-
5fa0: 6d 61 70 20 65 6e 74 72 79 20 66 6f 72 20 61 20  map entry for a 
5fb0: 0a 2a 2a 20 64 61 74 61 62 61 73 65 20 70 61 67  .** database pag
5fc0: 65 2e 20 54 68 65 20 66 69 72 73 74 20 61 72 67  e. The first arg
5fd0: 75 6d 65 6e 74 20 74 6f 20 65 61 63 68 20 69 73  ument to each is
5fe0: 20 74 68 65 20 6e 75 6d 62 65 72 20 6f 66 20 75   the number of u
5ff0: 73 61 62 6c 65 0a 2a 2a 20 62 79 74 65 73 20 6f  sable.** bytes o
6000: 6e 20 65 61 63 68 20 70 61 67 65 20 6f 66 20 74  n each page of t
6010: 68 65 20 64 61 74 61 62 61 73 65 20 28 6f 66 74  he database (oft
6020: 65 6e 20 31 30 32 34 29 2e 20 54 68 65 20 73 65  en 1024). The se
6030: 63 6f 6e 64 20 69 73 20 74 68 65 0a 2a 2a 20 70  cond is the.** p
6040: 61 67 65 20 6e 75 6d 62 65 72 20 74 6f 20 6c 6f  age number to lo
6050: 6f 6b 20 75 70 20 69 6e 20 74 68 65 20 70 6f 69  ok up in the poi
6060: 6e 74 65 72 20 6d 61 70 2e 0a 2a 2a 0a 2a 2a 20  nter map..**.** 
6070: 50 54 52 4d 41 50 5f 50 41 47 45 4e 4f 20 72 65  PTRMAP_PAGENO re
6080: 74 75 72 6e 73 20 74 68 65 20 64 61 74 61 62 61  turns the databa
6090: 73 65 20 70 61 67 65 20 6e 75 6d 62 65 72 20 6f  se page number o
60a0: 66 20 74 68 65 20 70 6f 69 6e 74 65 72 2d 6d 61  f the pointer-ma
60b0: 70 0a 2a 2a 20 70 61 67 65 20 74 68 61 74 20 73  p.** page that s
60c0: 74 6f 72 65 73 20 74 68 65 20 72 65 71 75 69 72  tores the requir
60d0: 65 64 20 70 6f 69 6e 74 65 72 2e 20 50 54 52 4d  ed pointer. PTRM
60e0: 41 50 5f 50 54 52 4f 46 46 53 45 54 20 72 65 74  AP_PTROFFSET ret
60f0: 75 72 6e 73 0a 2a 2a 20 74 68 65 20 6f 66 66 73  urns.** the offs
6100: 65 74 20 6f 66 20 74 68 65 20 72 65 71 75 65 73  et of the reques
6110: 74 65 64 20 6d 61 70 20 65 6e 74 72 79 2e 0a 2a  ted map entry..*
6120: 2a 0a 2a 2a 20 49 66 20 74 68 65 20 70 67 6e 6f  *.** If the pgno
6130: 20 61 72 67 75 6d 65 6e 74 20 70 61 73 73 65 64   argument passed
6140: 20 74 6f 20 50 54 52 4d 41 50 5f 50 41 47 45 4e   to PTRMAP_PAGEN
6150: 4f 20 69 73 20 61 20 70 6f 69 6e 74 65 72 2d 6d  O is a pointer-m
6160: 61 70 20 70 61 67 65 2c 0a 2a 2a 20 74 68 65 6e  ap page,.** then
6170: 20 70 67 6e 6f 20 69 73 20 72 65 74 75 72 6e 65   pgno is returne
6180: 64 2e 20 53 6f 20 28 70 67 6e 6f 3d 3d 50 54 52  d. So (pgno==PTR
6190: 4d 41 50 5f 50 41 47 45 4e 4f 28 70 67 73 7a 2c  MAP_PAGENO(pgsz,
61a0: 20 70 67 6e 6f 29 29 20 63 61 6e 20 62 65 0a 2a   pgno)) can be.*
61b0: 2a 20 75 73 65 64 20 74 6f 20 74 65 73 74 20 69  * used to test i
61c0: 66 20 70 67 6e 6f 20 69 73 20 61 20 70 6f 69 6e  f pgno is a poin
61d0: 74 65 72 2d 6d 61 70 20 70 61 67 65 2e 20 50 54  ter-map page. PT
61e0: 52 4d 41 50 5f 49 53 50 41 47 45 20 69 6d 70 6c  RMAP_ISPAGE impl
61f0: 65 6d 65 6e 74 73 0a 2a 2a 20 74 68 69 73 20 74  ements.** this t
6200: 65 73 74 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20  est..*/.#define 
6210: 50 54 52 4d 41 50 5f 50 41 47 45 4e 4f 28 70 42  PTRMAP_PAGENO(pB
6220: 74 2c 20 70 67 6e 6f 29 20 70 74 72 6d 61 70 50  t, pgno) ptrmapP
6230: 61 67 65 6e 6f 28 70 42 74 2c 20 70 67 6e 6f 29  ageno(pBt, pgno)
6240: 0a 23 64 65 66 69 6e 65 20 50 54 52 4d 41 50 5f  .#define PTRMAP_
6250: 50 54 52 4f 46 46 53 45 54 28 70 67 70 74 72 6d  PTROFFSET(pgptrm
6260: 61 70 2c 20 70 67 6e 6f 29 20 28 35 2a 28 70 67  ap, pgno) (5*(pg
6270: 6e 6f 2d 70 67 70 74 72 6d 61 70 2d 31 29 29 0a  no-pgptrmap-1)).
6280: 23 64 65 66 69 6e 65 20 50 54 52 4d 41 50 5f 49  #define PTRMAP_I
6290: 53 50 41 47 45 28 70 42 74 2c 20 70 67 6e 6f 29  SPAGE(pBt, pgno)
62a0: 20 28 50 54 52 4d 41 50 5f 50 41 47 45 4e 4f 28   (PTRMAP_PAGENO(
62b0: 28 70 42 74 29 2c 28 70 67 6e 6f 29 29 3d 3d 28  (pBt),(pgno))==(
62c0: 70 67 6e 6f 29 29 0a 0a 2f 2a 0a 2a 2a 20 54 68  pgno))../*.** Th
62d0: 65 20 70 6f 69 6e 74 65 72 20 6d 61 70 20 69 73  e pointer map is
62e0: 20 61 20 6c 6f 6f 6b 75 70 20 74 61 62 6c 65 20   a lookup table 
62f0: 74 68 61 74 20 69 64 65 6e 74 69 66 69 65 73 20  that identifies 
6300: 74 68 65 20 70 61 72 65 6e 74 20 70 61 67 65 20  the parent page 
6310: 66 6f 72 0a 2a 2a 20 65 61 63 68 20 63 68 69 6c  for.** each chil
6320: 64 20 70 61 67 65 20 69 6e 20 74 68 65 20 64 61  d page in the da
6330: 74 61 62 61 73 65 20 66 69 6c 65 2e 20 20 54 68  tabase file.  Th
6340: 65 20 70 61 72 65 6e 74 20 70 61 67 65 20 69 73  e parent page is
6350: 20 74 68 65 20 70 61 67 65 20 74 68 61 74 0a 2a   the page that.*
6360: 2a 20 63 6f 6e 74 61 69 6e 73 20 61 20 70 6f 69  * contains a poi
6370: 6e 74 65 72 20 74 6f 20 74 68 65 20 63 68 69 6c  nter to the chil
6380: 64 2e 20 20 45 76 65 72 79 20 70 61 67 65 20 69  d.  Every page i
6390: 6e 20 74 68 65 20 64 61 74 61 62 61 73 65 20 63  n the database c
63a0: 6f 6e 74 61 69 6e 73 0a 2a 2a 20 30 20 6f 72 20  ontains.** 0 or 
63b0: 31 20 70 61 72 65 6e 74 20 70 61 67 65 73 2e 20  1 parent pages. 
63c0: 20 28 49 6e 20 74 68 69 73 20 63 6f 6e 74 65 78   (In this contex
63d0: 74 20 27 64 61 74 61 62 61 73 65 20 70 61 67 65  t 'database page
63e0: 27 20 72 65 66 65 72 73 0a 2a 2a 20 74 6f 20 61  ' refers.** to a
63f0: 6e 79 20 70 61 67 65 20 74 68 61 74 20 69 73 20  ny page that is 
6400: 6e 6f 74 20 70 61 72 74 20 6f 66 20 74 68 65 20  not part of the 
6410: 70 6f 69 6e 74 65 72 20 6d 61 70 20 69 74 73 65  pointer map itse
6420: 6c 66 2e 29 20 20 45 61 63 68 20 70 6f 69 6e 74  lf.)  Each point
6430: 65 72 20 6d 61 70 0a 2a 2a 20 65 6e 74 72 79 20  er map.** entry 
6440: 63 6f 6e 73 69 73 74 73 20 6f 66 20 61 20 73 69  consists of a si
6450: 6e 67 6c 65 20 62 79 74 65 20 27 74 79 70 65 27  ngle byte 'type'
6460: 20 61 6e 64 20 61 20 34 20 62 79 74 65 20 70 61   and a 4 byte pa
6470: 72 65 6e 74 20 70 61 67 65 20 6e 75 6d 62 65 72  rent page number
6480: 2e 0a 2a 2a 20 54 68 65 20 50 54 52 4d 41 50 5f  ..** The PTRMAP_
6490: 58 58 58 20 69 64 65 6e 74 69 66 69 65 72 73 20  XXX identifiers 
64a0: 62 65 6c 6f 77 20 61 72 65 20 74 68 65 20 76 61  below are the va
64b0: 6c 69 64 20 74 79 70 65 73 2e 0a 2a 2a 0a 2a 2a  lid types..**.**
64c0: 20 54 68 65 20 70 75 72 70 6f 73 65 20 6f 66 20   The purpose of 
64d0: 74 68 65 20 70 6f 69 6e 74 65 72 20 6d 61 70 20  the pointer map 
64e0: 69 73 20 74 6f 20 66 61 63 69 6c 69 74 79 20 6d  is to facility m
64f0: 6f 76 69 6e 67 20 70 61 67 65 73 20 66 72 6f 6d  oving pages from
6500: 20 6f 6e 65 0a 2a 2a 20 70 6f 73 69 74 69 6f 6e   one.** position
6510: 20 69 6e 20 74 68 65 20 66 69 6c 65 20 74 6f 20   in the file to 
6520: 61 6e 6f 74 68 65 72 20 61 73 20 70 61 72 74 20  another as part 
6530: 6f 66 20 61 75 74 6f 76 61 63 75 75 6d 2e 20 20  of autovacuum.  
6540: 57 68 65 6e 20 61 20 70 61 67 65 0a 2a 2a 20 69  When a page.** i
6550: 73 20 6d 6f 76 65 64 2c 20 74 68 65 20 70 6f 69  s moved, the poi
6560: 6e 74 65 72 20 69 6e 20 69 74 73 20 70 61 72 65  nter in its pare
6570: 6e 74 20 6d 75 73 74 20 62 65 20 75 70 64 61 74  nt must be updat
6580: 65 64 20 74 6f 20 70 6f 69 6e 74 20 74 6f 20 74  ed to point to t
6590: 68 65 0a 2a 2a 20 6e 65 77 20 6c 6f 63 61 74 69  he.** new locati
65a0: 6f 6e 2e 20 20 54 68 65 20 70 6f 69 6e 74 65 72  on.  The pointer
65b0: 20 6d 61 70 20 69 73 20 75 73 65 64 20 74 6f 20   map is used to 
65c0: 6c 6f 63 61 74 65 20 74 68 65 20 70 61 72 65 6e  locate the paren
65d0: 74 20 70 61 67 65 20 71 75 69 63 6b 6c 79 2e 0a  t page quickly..
65e0: 2a 2a 0a 2a 2a 20 50 54 52 4d 41 50 5f 52 4f 4f  **.** PTRMAP_ROO
65f0: 54 50 41 47 45 3a 20 54 68 65 20 64 61 74 61 62  TPAGE: The datab
6600: 61 73 65 20 70 61 67 65 20 69 73 20 61 20 72 6f  ase page is a ro
6610: 6f 74 2d 70 61 67 65 2e 20 54 68 65 20 70 61 67  ot-page. The pag
6620: 65 2d 6e 75 6d 62 65 72 20 69 73 20 6e 6f 74 0a  e-number is not.
6630: 2a 2a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  **              
6640: 20 20 20 20 75 73 65 64 20 69 6e 20 74 68 69 73      used in this
6650: 20 63 61 73 65 2e 0a 2a 2a 0a 2a 2a 20 50 54 52   case..**.** PTR
6660: 4d 41 50 5f 46 52 45 45 50 41 47 45 3a 20 54 68  MAP_FREEPAGE: Th
6670: 65 20 64 61 74 61 62 61 73 65 20 70 61 67 65 20  e database page 
6680: 69 73 20 61 6e 20 75 6e 75 73 65 64 20 28 66 72  is an unused (fr
6690: 65 65 29 20 70 61 67 65 2e 20 54 68 65 20 70 61  ee) page. The pa
66a0: 67 65 2d 6e 75 6d 62 65 72 20 0a 2a 2a 20 20 20  ge-number .**   
66b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 69                 i
66c0: 73 20 6e 6f 74 20 75 73 65 64 20 69 6e 20 74 68  s not used in th
66d0: 69 73 20 63 61 73 65 2e 0a 2a 2a 0a 2a 2a 20 50  is case..**.** P
66e0: 54 52 4d 41 50 5f 4f 56 45 52 46 4c 4f 57 31 3a  TRMAP_OVERFLOW1:
66f0: 20 54 68 65 20 64 61 74 61 62 61 73 65 20 70 61   The database pa
6700: 67 65 20 69 73 20 74 68 65 20 66 69 72 73 74 20  ge is the first 
6710: 70 61 67 65 20 69 6e 20 61 20 6c 69 73 74 20 6f  page in a list o
6720: 66 20 0a 2a 2a 20 20 20 20 20 20 20 20 20 20 20  f .**           
6730: 20 20 20 20 20 20 20 20 6f 76 65 72 66 6c 6f 77          overflow
6740: 20 70 61 67 65 73 2e 20 54 68 65 20 70 61 67 65   pages. The page
6750: 20 6e 75 6d 62 65 72 20 69 64 65 6e 74 69 66 69   number identifi
6760: 65 73 20 74 68 65 20 70 61 67 65 20 74 68 61 74  es the page that
6770: 0a 2a 2a 20 20 20 20 20 20 20 20 20 20 20 20 20  .**             
6780: 20 20 20 20 20 20 63 6f 6e 74 61 69 6e 73 20 74        contains t
6790: 68 65 20 63 65 6c 6c 20 77 69 74 68 20 61 20 70  he cell with a p
67a0: 6f 69 6e 74 65 72 20 74 6f 20 74 68 69 73 20 6f  ointer to this o
67b0: 76 65 72 66 6c 6f 77 20 70 61 67 65 2e 0a 2a 2a  verflow page..**
67c0: 0a 2a 2a 20 50 54 52 4d 41 50 5f 4f 56 45 52 46  .** PTRMAP_OVERF
67d0: 4c 4f 57 32 3a 20 54 68 65 20 64 61 74 61 62 61  LOW2: The databa
67e0: 73 65 20 70 61 67 65 20 69 73 20 74 68 65 20 73  se page is the s
67f0: 65 63 6f 6e 64 20 6f 72 20 6c 61 74 65 72 20 70  econd or later p
6800: 61 67 65 20 69 6e 20 61 20 6c 69 73 74 20 6f 66  age in a list of
6810: 0a 2a 2a 20 20 20 20 20 20 20 20 20 20 20 20 20  .**             
6820: 20 20 20 20 20 20 6f 76 65 72 66 6c 6f 77 20 70        overflow p
6830: 61 67 65 73 2e 20 54 68 65 20 70 61 67 65 2d 6e  ages. The page-n
6840: 75 6d 62 65 72 20 69 64 65 6e 74 69 66 69 65 73  umber identifies
6850: 20 74 68 65 20 70 72 65 76 69 6f 75 73 0a 2a 2a   the previous.**
6860: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
6870: 20 20 20 70 61 67 65 20 69 6e 20 74 68 65 20 6f     page in the o
6880: 76 65 72 66 6c 6f 77 20 70 61 67 65 20 6c 69 73  verflow page lis
6890: 74 2e 0a 2a 2a 0a 2a 2a 20 50 54 52 4d 41 50 5f  t..**.** PTRMAP_
68a0: 42 54 52 45 45 3a 20 54 68 65 20 64 61 74 61 62  BTREE: The datab
68b0: 61 73 65 20 70 61 67 65 20 69 73 20 61 20 6e 6f  ase page is a no
68c0: 6e 2d 72 6f 6f 74 20 62 74 72 65 65 20 70 61 67  n-root btree pag
68d0: 65 2e 20 54 68 65 20 70 61 67 65 20 6e 75 6d 62  e. The page numb
68e0: 65 72 0a 2a 2a 20 20 20 20 20 20 20 20 20 20 20  er.**           
68f0: 20 20 20 20 69 64 65 6e 74 69 66 69 65 73 20 74      identifies t
6900: 68 65 20 70 61 72 65 6e 74 20 70 61 67 65 20 69  he parent page i
6910: 6e 20 74 68 65 20 62 74 72 65 65 2e 0a 2a 2f 0a  n the btree..*/.
6920: 23 64 65 66 69 6e 65 20 50 54 52 4d 41 50 5f 52  #define PTRMAP_R
6930: 4f 4f 54 50 41 47 45 20 31 0a 23 64 65 66 69 6e  OOTPAGE 1.#defin
6940: 65 20 50 54 52 4d 41 50 5f 46 52 45 45 50 41 47  e PTRMAP_FREEPAG
6950: 45 20 32 0a 23 64 65 66 69 6e 65 20 50 54 52 4d  E 2.#define PTRM
6960: 41 50 5f 4f 56 45 52 46 4c 4f 57 31 20 33 0a 23  AP_OVERFLOW1 3.#
6970: 64 65 66 69 6e 65 20 50 54 52 4d 41 50 5f 4f 56  define PTRMAP_OV
6980: 45 52 46 4c 4f 57 32 20 34 0a 23 64 65 66 69 6e  ERFLOW2 4.#defin
6990: 65 20 50 54 52 4d 41 50 5f 42 54 52 45 45 20 35  e PTRMAP_BTREE 5
69a0: 0a 0a 2f 2a 20 41 20 62 75 6e 63 68 20 6f 66 20  ../* A bunch of 
69b0: 61 73 73 65 72 74 28 29 20 73 74 61 74 65 6d 65  assert() stateme
69c0: 6e 74 73 20 74 6f 20 63 68 65 63 6b 20 74 68 65  nts to check the
69d0: 20 74 72 61 6e 73 61 63 74 69 6f 6e 20 73 74 61   transaction sta
69e0: 74 65 20 76 61 72 69 61 62 6c 65 73 0a 2a 2a 20  te variables.** 
69f0: 6f 66 20 68 61 6e 64 6c 65 20 70 20 28 74 79 70  of handle p (typ
6a00: 65 20 42 74 72 65 65 2a 29 20 61 72 65 20 69 6e  e Btree*) are in
6a10: 74 65 72 6e 61 6c 6c 79 20 63 6f 6e 73 69 73 74  ternally consist
6a20: 65 6e 74 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20  ent..*/.#define 
6a30: 62 74 72 65 65 49 6e 74 65 67 72 69 74 79 28 70  btreeIntegrity(p
6a40: 29 20 5c 0a 20 20 61 73 73 65 72 74 28 20 70 2d  ) \.  assert( p-
6a50: 3e 70 42 74 2d 3e 69 6e 54 72 61 6e 73 61 63 74  >pBt->inTransact
6a60: 69 6f 6e 21 3d 54 52 41 4e 53 5f 4e 4f 4e 45 20  ion!=TRANS_NONE 
6a70: 7c 7c 20 70 2d 3e 70 42 74 2d 3e 6e 54 72 61 6e  || p->pBt->nTran
6a80: 73 61 63 74 69 6f 6e 3d 3d 30 20 29 3b 20 5c 0a  saction==0 ); \.
6a90: 20 20 61 73 73 65 72 74 28 20 70 2d 3e 70 42 74    assert( p->pBt
6aa0: 2d 3e 69 6e 54 72 61 6e 73 61 63 74 69 6f 6e 3e  ->inTransaction>
6ab0: 3d 70 2d 3e 69 6e 54 72 61 6e 73 20 29 3b 20 0a  =p->inTrans ); .
6ac0: 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 20 49 53 41 55  ../*.** The ISAU
6ad0: 54 4f 56 41 43 55 55 4d 20 6d 61 63 72 6f 20 69  TOVACUUM macro i
6ae0: 73 20 75 73 65 64 20 77 69 74 68 69 6e 20 62 61  s used within ba
6af0: 6c 61 6e 63 65 5f 6e 6f 6e 72 6f 6f 74 28 29 20  lance_nonroot() 
6b00: 74 6f 20 64 65 74 65 72 6d 69 6e 65 0a 2a 2a 20  to determine.** 
6b10: 69 66 20 74 68 65 20 64 61 74 61 62 61 73 65 20  if the database 
6b20: 73 75 70 70 6f 72 74 73 20 61 75 74 6f 2d 76 61  supports auto-va
6b30: 63 75 75 6d 20 6f 72 20 6e 6f 74 2e 20 42 65 63  cuum or not. Bec
6b40: 61 75 73 65 20 69 74 20 69 73 20 75 73 65 64 0a  ause it is used.
6b50: 2a 2a 20 77 69 74 68 69 6e 20 61 6e 20 65 78 70  ** within an exp
6b60: 72 65 73 73 69 6f 6e 20 74 68 61 74 20 69 73 20  ression that is 
6b70: 61 6e 20 61 72 67 75 6d 65 6e 74 20 74 6f 20 61  an argument to a
6b80: 6e 6f 74 68 65 72 20 6d 61 63 72 6f 20 0a 2a 2a  nother macro .**
6b90: 20 28 73 71 6c 69 74 65 4d 61 6c 6c 6f 63 52 61   (sqliteMallocRa
6ba0: 77 29 2c 20 69 74 20 69 73 20 6e 6f 74 20 70 6f  w), it is not po
6bb0: 73 73 69 62 6c 65 20 74 6f 20 75 73 65 20 63 6f  ssible to use co
6bc0: 6e 64 69 74 69 6f 6e 61 6c 20 63 6f 6d 70 69 6c  nditional compil
6bd0: 61 74 69 6f 6e 2e 0a 2a 2a 20 53 6f 2c 20 74 68  ation..** So, th
6be0: 69 73 20 6d 61 63 72 6f 20 69 73 20 64 65 66 69  is macro is defi
6bf0: 6e 65 64 20 69 6e 73 74 65 61 64 2e 0a 2a 2f 0a  ned instead..*/.
6c00: 23 69 66 6e 64 65 66 20 53 51 4c 49 54 45 5f 4f  #ifndef SQLITE_O
6c10: 4d 49 54 5f 41 55 54 4f 56 41 43 55 55 4d 0a 23  MIT_AUTOVACUUM.#
6c20: 64 65 66 69 6e 65 20 49 53 41 55 54 4f 56 41 43  define ISAUTOVAC
6c30: 55 55 4d 20 28 70 42 74 2d 3e 61 75 74 6f 56 61  UUM (pBt->autoVa
6c40: 63 75 75 6d 29 0a 23 65 6c 73 65 0a 23 64 65 66  cuum).#else.#def
6c50: 69 6e 65 20 49 53 41 55 54 4f 56 41 43 55 55 4d  ine ISAUTOVACUUM
6c60: 20 30 0a 23 65 6e 64 69 66 0a 0a 0a 2f 2a 0a 2a   0.#endif.../*.*
6c70: 2a 20 54 68 69 73 20 73 74 72 75 63 74 75 72 65  * This structure
6c80: 20 69 73 20 70 61 73 73 65 64 20 61 72 6f 75 6e   is passed aroun
6c90: 64 20 74 68 72 6f 75 67 68 20 61 6c 6c 20 74 68  d through all th
6ca0: 65 20 73 61 6e 69 74 79 20 63 68 65 63 6b 69 6e  e sanity checkin
6cb0: 67 20 72 6f 75 74 69 6e 65 73 0a 2a 2a 20 69 6e  g routines.** in
6cc0: 20 6f 72 64 65 72 20 74 6f 20 6b 65 65 70 20 74   order to keep t
6cd0: 72 61 63 6b 20 6f 66 20 73 6f 6d 65 20 67 6c 6f  rack of some glo
6ce0: 62 61 6c 20 73 74 61 74 65 20 69 6e 66 6f 72 6d  bal state inform
6cf0: 61 74 69 6f 6e 2e 0a 2a 2f 0a 74 79 70 65 64 65  ation..*/.typede
6d00: 66 20 73 74 72 75 63 74 20 49 6e 74 65 67 72 69  f struct Integri
6d10: 74 79 43 6b 20 49 6e 74 65 67 72 69 74 79 43 6b  tyCk IntegrityCk
6d20: 3b 0a 73 74 72 75 63 74 20 49 6e 74 65 67 72 69  ;.struct Integri
6d30: 74 79 43 6b 20 7b 0a 20 20 42 74 53 68 61 72 65  tyCk {.  BtShare
6d40: 64 20 2a 70 42 74 3b 20 20 20 20 2f 2a 20 54 68  d *pBt;    /* Th
6d50: 65 20 74 72 65 65 20 62 65 69 6e 67 20 63 68 65  e tree being che
6d60: 63 6b 65 64 20 6f 75 74 20 2a 2f 0a 20 20 50 61  cked out */.  Pa
6d70: 67 65 72 20 2a 70 50 61 67 65 72 3b 20 20 20 20  ger *pPager;    
6d80: 2f 2a 20 54 68 65 20 61 73 73 6f 63 69 61 74 65  /* The associate
6d90: 64 20 70 61 67 65 72 2e 20 20 41 6c 73 6f 20 61  d pager.  Also a
6da0: 63 63 65 73 73 69 62 6c 65 20 62 79 20 70 42 74  ccessible by pBt
6db0: 2d 3e 70 50 61 67 65 72 20 2a 2f 0a 20 20 50 67  ->pPager */.  Pg
6dc0: 6e 6f 20 6e 50 61 67 65 3b 20 20 20 20 20 20 20  no nPage;       
6dd0: 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 70 61 67  /* Number of pag
6de0: 65 73 20 69 6e 20 74 68 65 20 64 61 74 61 62 61  es in the databa
6df0: 73 65 20 2a 2f 0a 20 20 69 6e 74 20 2a 61 6e 52  se */.  int *anR
6e00: 65 66 3b 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d  ef;       /* Num
6e10: 62 65 72 20 6f 66 20 74 69 6d 65 73 20 65 61 63  ber of times eac
6e20: 68 20 70 61 67 65 20 69 73 20 72 65 66 65 72 65  h page is refere
6e30: 6e 63 65 64 20 2a 2f 0a 20 20 69 6e 74 20 6d 78  nced */.  int mx
6e40: 45 72 72 3b 20 20 20 20 20 20 20 20 2f 2a 20 53  Err;        /* S
6e50: 74 6f 70 20 61 63 63 75 6d 75 6c 61 74 69 6e 67  top accumulating
6e60: 20 65 72 72 6f 72 73 20 77 68 65 6e 20 74 68 69   errors when thi
6e70: 73 20 72 65 61 63 68 65 73 20 7a 65 72 6f 20 2a  s reaches zero *
6e80: 2f 0a 20 20 69 6e 74 20 6e 45 72 72 3b 20 20 20  /.  int nErr;   
6e90: 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20        /* Number 
6ea0: 6f 66 20 6d 65 73 73 61 67 65 73 20 77 72 69 74  of messages writ
6eb0: 74 65 6e 20 74 6f 20 7a 45 72 72 4d 73 67 20 73  ten to zErrMsg s
6ec0: 6f 20 66 61 72 20 2a 2f 0a 20 20 69 6e 74 20 6d  o far */.  int m
6ed0: 61 6c 6c 6f 63 46 61 69 6c 65 64 3b 20 2f 2a 20  allocFailed; /* 
6ee0: 41 20 6d 65 6d 6f 72 79 20 61 6c 6c 6f 63 61 74  A memory allocat
6ef0: 69 6f 6e 20 65 72 72 6f 72 20 68 61 73 20 6f 63  ion error has oc
6f00: 63 75 72 72 65 64 20 2a 2f 0a 20 20 53 74 72 41  curred */.  StrA
6f10: 63 63 75 6d 20 65 72 72 4d 73 67 3b 20 20 2f 2a  ccum errMsg;  /*
6f20: 20 41 63 63 75 6d 75 6c 61 74 65 20 74 68 65 20   Accumulate the 
6f30: 65 72 72 6f 72 20 6d 65 73 73 61 67 65 20 74 65  error message te
6f40: 78 74 20 68 65 72 65 20 2a 2f 0a 7d 3b 0a 0a 2f  xt here */.};../
6f50: 2a 0a 2a 2a 20 52 65 61 64 20 6f 72 20 77 72 69  *.** Read or wri
6f60: 74 65 20 61 20 74 77 6f 2d 20 61 6e 64 20 66 6f  te a two- and fo
6f70: 75 72 2d 62 79 74 65 20 62 69 67 2d 65 6e 64 69  ur-byte big-endi
6f80: 61 6e 20 69 6e 74 65 67 65 72 20 76 61 6c 75 65  an integer value
6f90: 73 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 67 65  s..*/.#define ge
6fa0: 74 32 62 79 74 65 28 78 29 20 20 20 28 28 78 29  t2byte(x)   ((x)
6fb0: 5b 30 5d 3c 3c 38 20 7c 20 28 78 29 5b 31 5d 29  [0]<<8 | (x)[1])
6fc0: 0a 23 64 65 66 69 6e 65 20 70 75 74 32 62 79 74  .#define put2byt
6fd0: 65 28 70 2c 76 29 20 28 28 70 29 5b 30 5d 20 3d  e(p,v) ((p)[0] =
6fe0: 20 28 75 38 29 28 28 76 29 3e 3e 38 29 2c 20 28   (u8)((v)>>8), (
6ff0: 70 29 5b 31 5d 20 3d 20 28 75 38 29 28 76 29 29  p)[1] = (u8)(v))
7000: 0a 23 64 65 66 69 6e 65 20 67 65 74 34 62 79 74  .#define get4byt
7010: 65 20 73 71 6c 69 74 65 33 47 65 74 34 62 79 74  e sqlite3Get4byt
7020: 65 0a 23 64 65 66 69 6e 65 20 70 75 74 34 62 79  e.#define put4by
7030: 74 65 20 73 71 6c 69 74 65 33 50 75 74 34 62 79  te sqlite3Put4by
7040: 74 65 0a                                         te.