/ Hex Artifact Content
Login

Artifact 4330c19b8314545fdb209cc77e2a57f6a5290e9c:


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 31 33 20 32 30 30 37  nt.h,v 1.13 2007
0190: 2f 30 38 2f 33 30 20 30 31 3a 31 39 3a 35 39 20  /08/30 01:19:59 
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 41 6c 6c 20 6f 66 20 74 68 65 20 69 6e 74 65   All of the inte
0d10: 67 65 72 20 76 61 6c 75 65 73 20 61 72 65 20 62  ger values are b
0d20: 69 67 2d 65 6e 64 69 61 6e 20 28 6d 6f 73 74 20  ig-endian (most 
0d30: 73 69 67 6e 69 66 69 63 61 6e 74 20 62 79 74 65  significant byte
0d40: 20 66 69 72 73 74 29 2e 0a 2a 2a 0a 2a 2a 20 54   first)..**.** T
0d50: 68 65 20 66 69 6c 65 20 63 68 61 6e 67 65 20 63  he file change c
0d60: 6f 75 6e 74 65 72 20 69 73 20 69 6e 63 72 65 6d  ounter is increm
0d70: 65 6e 74 65 64 20 77 68 65 6e 20 74 68 65 20 64  ented when the d
0d80: 61 74 61 62 61 73 65 20 69 73 20 63 68 61 6e 67  atabase is chang
0d90: 65 64 0a 2a 2a 20 54 68 69 73 20 63 6f 75 6e 74  ed.** This count
0da0: 65 72 20 61 6c 6c 6f 77 73 20 6f 74 68 65 72 20  er allows other 
0db0: 70 72 6f 63 65 73 73 65 73 20 74 6f 20 6b 6e 6f  processes to kno
0dc0: 77 20 77 68 65 6e 20 74 68 65 20 66 69 6c 65 20  w when the file 
0dd0: 68 61 73 20 63 68 61 6e 67 65 64 0a 2a 2a 20 61  has changed.** a
0de0: 6e 64 20 74 68 75 73 20 77 68 65 6e 20 74 68 65  nd thus when the
0df0: 79 20 6e 65 65 64 20 74 6f 20 66 6c 75 73 68 20  y need to flush 
0e00: 74 68 65 69 72 20 63 61 63 68 65 2e 0a 2a 2a 0a  their cache..**.
0e10: 2a 2a 20 54 68 65 20 6d 61 78 20 65 6d 62 65 64  ** The max embed
0e20: 64 65 64 20 70 61 79 6c 6f 61 64 20 66 72 61 63  ded payload frac
0e30: 74 69 6f 6e 20 69 73 20 74 68 65 20 61 6d 6f 75  tion is the amou
0e40: 6e 74 20 6f 66 20 74 68 65 20 74 6f 74 61 6c 20  nt of the total 
0e50: 75 73 61 62 6c 65 0a 2a 2a 20 73 70 61 63 65 20  usable.** space 
0e60: 69 6e 20 61 20 70 61 67 65 20 74 68 61 74 20 63  in a page that c
0e70: 61 6e 20 62 65 20 63 6f 6e 73 75 6d 65 64 20 62  an be consumed b
0e80: 79 20 61 20 73 69 6e 67 6c 65 20 63 65 6c 6c 20  y a single cell 
0e90: 66 6f 72 20 73 74 61 6e 64 61 72 64 0a 2a 2a 20  for standard.** 
0ea0: 42 2d 74 72 65 65 20 28 6e 6f 6e 2d 4c 45 41 46  B-tree (non-LEAF
0eb0: 44 41 54 41 29 20 74 61 62 6c 65 73 2e 20 20 41  DATA) tables.  A
0ec0: 20 76 61 6c 75 65 20 6f 66 20 32 35 35 20 6d 65   value of 255 me
0ed0: 61 6e 73 20 31 30 30 25 2e 20 20 54 68 65 20 64  ans 100%.  The d
0ee0: 65 66 61 75 6c 74 0a 2a 2a 20 69 73 20 74 6f 20  efault.** is to 
0ef0: 6c 69 6d 69 74 20 74 68 65 20 6d 61 78 69 6d 75  limit the maximu
0f00: 6d 20 63 65 6c 6c 20 73 69 7a 65 20 73 6f 20 74  m cell size so t
0f10: 68 61 74 20 61 74 20 6c 65 61 73 74 20 34 20 63  hat at least 4 c
0f20: 65 6c 6c 73 20 77 69 6c 6c 20 66 69 74 0a 2a 2a  ells will fit.**
0f30: 20 6f 6e 20 6f 6e 65 20 70 61 67 65 2e 20 20 54   on one page.  T
0f40: 68 75 73 20 74 68 65 20 64 65 66 61 75 6c 74 20  hus the default 
0f50: 6d 61 78 20 65 6d 62 65 64 64 65 64 20 70 61 79  max embedded pay
0f60: 6c 6f 61 64 20 66 72 61 63 74 69 6f 6e 20 69 73  load fraction is
0f70: 20 36 34 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 74 68   64..**.** If th
0f80: 65 20 70 61 79 6c 6f 61 64 20 66 6f 72 20 61 20  e payload for a 
0f90: 63 65 6c 6c 20 69 73 20 6c 61 72 67 65 72 20 74  cell is larger t
0fa0: 68 61 6e 20 74 68 65 20 6d 61 78 20 70 61 79 6c  han the max payl
0fb0: 6f 61 64 2c 20 74 68 65 6e 20 65 78 74 72 61 0a  oad, then extra.
0fc0: 2a 2a 20 70 61 79 6c 6f 61 64 20 69 73 20 73 70  ** payload is sp
0fd0: 69 6c 6c 65 64 20 74 6f 20 6f 76 65 72 66 6c 6f  illed to overflo
0fe0: 77 20 70 61 67 65 73 2e 20 20 4f 6e 63 65 20 61  w pages.  Once a
0ff0: 6e 20 6f 76 65 72 66 6c 6f 77 20 70 61 67 65 20  n overflow page 
1000: 69 73 20 61 6c 6c 6f 63 61 74 65 64 2c 0a 2a 2a  is allocated,.**
1010: 20 61 73 20 6d 61 6e 79 20 62 79 74 65 73 20 61   as many bytes a
1020: 73 20 70 6f 73 73 69 62 6c 65 20 61 72 65 20 6d  s possible are m
1030: 6f 76 65 64 20 69 6e 74 6f 20 74 68 65 20 6f 76  oved into the ov
1040: 65 72 66 6c 6f 77 20 70 61 67 65 73 20 77 69 74  erflow pages wit
1050: 68 6f 75 74 20 6c 65 74 74 69 6e 67 0a 2a 2a 20  hout letting.** 
1060: 74 68 65 20 63 65 6c 6c 20 73 69 7a 65 20 64 72  the cell size dr
1070: 6f 70 20 62 65 6c 6f 77 20 74 68 65 20 6d 69 6e  op below the min
1080: 20 65 6d 62 65 64 64 65 64 20 70 61 79 6c 6f 61   embedded payloa
1090: 64 20 66 72 61 63 74 69 6f 6e 2e 0a 2a 2a 0a 2a  d fraction..**.*
10a0: 2a 20 54 68 65 20 6d 69 6e 20 6c 65 61 66 20 70  * The min leaf p
10b0: 61 79 6c 6f 61 64 20 66 72 61 63 74 69 6f 6e 20  ayload fraction 
10c0: 69 73 20 6c 69 6b 65 20 74 68 65 20 6d 69 6e 20  is like the min 
10d0: 65 6d 62 65 64 64 65 64 20 70 61 79 6c 6f 61 64  embedded payload
10e0: 20 66 72 61 63 74 69 6f 6e 0a 2a 2a 20 65 78 63   fraction.** exc
10f0: 65 70 74 20 74 68 61 74 20 69 74 20 61 70 70 6c  ept that it appl
1100: 69 65 73 20 74 6f 20 6c 65 61 66 20 6e 6f 64 65  ies to leaf node
1110: 73 20 69 6e 20 61 20 4c 45 41 46 44 41 54 41 20  s in a LEAFDATA 
1120: 74 72 65 65 2e 20 20 54 68 65 20 6d 61 78 69 6d  tree.  The maxim
1130: 75 6d 0a 2a 2a 20 70 61 79 6c 6f 61 64 20 66 72  um.** payload fr
1140: 61 63 74 69 6f 6e 20 66 6f 72 20 61 20 4c 45 41  action for a LEA
1150: 46 44 41 54 41 20 74 72 65 65 20 69 73 20 61 6c  FDATA tree is al
1160: 77 61 79 73 20 31 30 30 25 20 28 6f 72 20 32 35  ways 100% (or 25
1170: 35 29 20 61 6e 64 20 69 74 0a 2a 2a 20 6e 6f 74  5) and it.** not
1180: 20 73 70 65 63 69 66 69 65 64 20 69 6e 20 74 68   specified in th
1190: 65 20 68 65 61 64 65 72 2e 0a 2a 2a 0a 2a 2a 20  e header..**.** 
11a0: 45 61 63 68 20 62 74 72 65 65 20 70 61 67 65 73  Each btree pages
11b0: 20 69 73 20 64 69 76 69 64 65 64 20 69 6e 74 6f   is divided into
11c0: 20 74 68 72 65 65 20 73 65 63 74 69 6f 6e 73 3a   three sections:
11d0: 20 20 54 68 65 20 68 65 61 64 65 72 2c 20 74 68    The header, th
11e0: 65 0a 2a 2a 20 63 65 6c 6c 20 70 6f 69 6e 74 65  e.** cell pointe
11f0: 72 20 61 72 72 61 79 2c 20 61 6e 64 20 74 68 65  r array, and the
1200: 20 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 20 61 72   cell content ar
1210: 65 61 2e 20 20 50 61 67 65 20 31 20 61 6c 73 6f  ea.  Page 1 also
1220: 20 68 61 73 20 61 20 31 30 30 2d 62 79 74 65 0a   has a 100-byte.
1230: 2a 2a 20 66 69 6c 65 20 68 65 61 64 65 72 20 74  ** file header t
1240: 68 61 74 20 6f 63 63 75 72 73 20 62 65 66 6f 72  hat occurs befor
1250: 65 20 74 68 65 20 70 61 67 65 20 68 65 61 64 65  e the page heade
1260: 72 2e 0a 2a 2a 0a 2a 2a 20 20 20 20 20 20 7c 2d  r..**.**      |-
1270: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 7c  ---------------|
1280: 0a 2a 2a 20 20 20 20 20 20 7c 20 66 69 6c 65 20  .**      | file 
1290: 68 65 61 64 65 72 20 20 20 20 7c 20 20 20 31 30  header    |   10
12a0: 30 20 62 79 74 65 73 2e 20 20 50 61 67 65 20 31  0 bytes.  Page 1
12b0: 20 6f 6e 6c 79 2e 0a 2a 2a 20 20 20 20 20 20 7c   only..**      |
12c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
12d0: 7c 0a 2a 2a 20 20 20 20 20 20 7c 20 70 61 67 65  |.**      | page
12e0: 20 68 65 61 64 65 72 20 20 20 20 7c 20 20 20 38   header    |   8
12f0: 20 62 79 74 65 73 20 66 6f 72 20 6c 65 61 76 65   bytes for leave
1300: 73 2e 20 20 31 32 20 62 79 74 65 73 20 66 6f 72  s.  12 bytes for
1310: 20 69 6e 74 65 72 69 6f 72 20 6e 6f 64 65 73 0a   interior nodes.
1320: 2a 2a 20 20 20 20 20 20 7c 2d 2d 2d 2d 2d 2d 2d  **      |-------
1330: 2d 2d 2d 2d 2d 2d 2d 2d 2d 7c 0a 2a 2a 20 20 20  ---------|.**   
1340: 20 20 20 7c 20 63 65 6c 6c 20 70 6f 69 6e 74 65     | cell pointe
1350: 72 20 20 20 7c 20 20 20 7c 20 20 32 20 62 79 74  r   |   |  2 byt
1360: 65 73 20 70 65 72 20 63 65 6c 6c 2e 20 20 53 6f  es per cell.  So
1370: 72 74 65 64 20 6f 72 64 65 72 2e 0a 2a 2a 20 20  rted order..**  
1380: 20 20 20 20 7c 20 61 72 72 61 79 20 20 20 20 20      | array     
1390: 20 20 20 20 20 7c 20 20 20 7c 20 20 47 72 6f 77       |   |  Grow
13a0: 73 20 64 6f 77 6e 77 61 72 64 0a 2a 2a 20 20 20  s downward.**   
13b0: 20 20 20 7c 20 20 20 20 20 20 20 20 20 20 20 20     |            
13c0: 20 20 20 20 7c 20 20 20 76 0a 2a 2a 20 20 20 20      |   v.**    
13d0: 20 20 7c 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d    |-------------
13e0: 2d 2d 2d 7c 0a 2a 2a 20 20 20 20 20 20 7c 20 75  ---|.**      | u
13f0: 6e 61 6c 6c 6f 63 61 74 65 64 20 20 20 20 7c 0a  nallocated    |.
1400: 2a 2a 20 20 20 20 20 20 7c 20 73 70 61 63 65 20  **      | space 
1410: 20 20 20 20 20 20 20 20 20 7c 0a 2a 2a 20 20 20           |.**   
1420: 20 20 20 7c 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d     |------------
1430: 2d 2d 2d 2d 7c 20 20 20 5e 20 20 47 72 6f 77 73  ----|   ^  Grows
1440: 20 75 70 77 61 72 64 73 0a 2a 2a 20 20 20 20 20   upwards.**     
1450: 20 7c 20 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 20   | cell content 
1460: 20 20 7c 20 20 20 7c 20 20 41 72 62 69 74 72 61    |   |  Arbitra
1470: 72 79 20 6f 72 64 65 72 20 69 6e 74 65 72 73 70  ry order intersp
1480: 65 72 73 65 64 20 77 69 74 68 20 66 72 65 65 62  ersed with freeb
1490: 6c 6f 63 6b 73 2e 0a 2a 2a 20 20 20 20 20 20 7c  locks..**      |
14a0: 20 61 72 65 61 20 20 20 20 20 20 20 20 20 20 20   area           
14b0: 7c 20 20 20 7c 20 20 61 6e 64 20 66 72 65 65 20  |   |  and free 
14c0: 73 70 61 63 65 20 66 72 61 67 6d 65 6e 74 73 2e  space fragments.
14d0: 0a 2a 2a 20 20 20 20 20 20 7c 2d 2d 2d 2d 2d 2d  .**      |------
14e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 7c 0a 2a 2a 0a 2a  ----------|.**.*
14f0: 2a 20 54 68 65 20 70 61 67 65 20 68 65 61 64 65  * The page heade
1500: 72 73 20 6c 6f 6f 6b 73 20 6c 69 6b 65 20 74 68  rs looks like th
1510: 69 73 3a 0a 2a 2a 0a 2a 2a 20 20 20 4f 46 46 53  is:.**.**   OFFS
1520: 45 54 20 20 20 53 49 5a 45 20 20 20 20 20 44 45  ET   SIZE     DE
1530: 53 43 52 49 50 54 49 4f 4e 0a 2a 2a 20 20 20 20  SCRIPTION.**    
1540: 20 20 30 20 20 20 20 20 20 20 31 20 20 20 20 20    0       1     
1550: 20 46 6c 61 67 73 2e 20 31 3a 20 69 6e 74 6b 65   Flags. 1: intke
1560: 79 2c 20 32 3a 20 7a 65 72 6f 64 61 74 61 2c 20  y, 2: zerodata, 
1570: 34 3a 20 6c 65 61 66 64 61 74 61 2c 20 38 3a 20  4: leafdata, 8: 
1580: 6c 65 61 66 0a 2a 2a 20 20 20 20 20 20 31 20 20  leaf.**      1  
1590: 20 20 20 20 20 32 20 20 20 20 20 20 62 79 74 65       2      byte
15a0: 20 6f 66 66 73 65 74 20 74 6f 20 74 68 65 20 66   offset to the f
15b0: 69 72 73 74 20 66 72 65 65 62 6c 6f 63 6b 0a 2a  irst freeblock.*
15c0: 2a 20 20 20 20 20 20 33 20 20 20 20 20 20 20 32  *      3       2
15d0: 20 20 20 20 20 20 6e 75 6d 62 65 72 20 6f 66 20        number of 
15e0: 63 65 6c 6c 73 20 6f 6e 20 74 68 69 73 20 70 61  cells on this pa
15f0: 67 65 0a 2a 2a 20 20 20 20 20 20 35 20 20 20 20  ge.**      5    
1600: 20 20 20 32 20 20 20 20 20 20 66 69 72 73 74 20     2      first 
1610: 62 79 74 65 20 6f 66 20 74 68 65 20 63 65 6c 6c  byte of the cell
1620: 20 63 6f 6e 74 65 6e 74 20 61 72 65 61 0a 2a 2a   content area.**
1630: 20 20 20 20 20 20 37 20 20 20 20 20 20 20 31 20        7       1 
1640: 20 20 20 20 20 6e 75 6d 62 65 72 20 6f 66 20 66       number of f
1650: 72 61 67 6d 65 6e 74 65 64 20 66 72 65 65 20 62  ragmented free b
1660: 79 74 65 73 0a 2a 2a 20 20 20 20 20 20 38 20 20  ytes.**      8  
1670: 20 20 20 20 20 34 20 20 20 20 20 20 52 69 67 68       4      Righ
1680: 74 20 63 68 69 6c 64 20 28 74 68 65 20 50 74 72  t child (the Ptr
1690: 28 4e 29 20 76 61 6c 75 65 29 2e 20 20 4f 6d 69  (N) value).  Omi
16a0: 74 74 65 64 20 6f 6e 20 6c 65 61 76 65 73 2e 0a  tted on leaves..
16b0: 2a 2a 0a 2a 2a 20 54 68 65 20 66 6c 61 67 73 20  **.** The flags 
16c0: 64 65 66 69 6e 65 20 74 68 65 20 66 6f 72 6d 61  define the forma
16d0: 74 20 6f 66 20 74 68 69 73 20 62 74 72 65 65 20  t of this btree 
16e0: 70 61 67 65 2e 20 20 54 68 65 20 6c 65 61 66 20  page.  The leaf 
16f0: 66 6c 61 67 20 6d 65 61 6e 73 20 74 68 61 74 0a  flag means that.
1700: 2a 2a 20 74 68 69 73 20 70 61 67 65 20 68 61 73  ** this page has
1710: 20 6e 6f 20 63 68 69 6c 64 72 65 6e 2e 20 20 54   no children.  T
1720: 68 65 20 7a 65 72 6f 64 61 74 61 20 66 6c 61 67  he zerodata flag
1730: 20 6d 65 61 6e 73 20 74 68 61 74 20 74 68 69 73   means that this
1740: 20 70 61 67 65 20 63 61 72 72 69 65 73 0a 2a 2a   page carries.**
1750: 20 6f 6e 6c 79 20 6b 65 79 73 20 61 6e 64 20 6e   only keys and n
1760: 6f 20 64 61 74 61 2e 20 20 54 68 65 20 69 6e 74  o data.  The int
1770: 6b 65 79 20 66 6c 61 67 20 6d 65 61 6e 73 20 74  key flag means t
1780: 68 61 74 20 74 68 65 20 6b 65 79 20 69 73 20 61  hat the key is a
1790: 20 69 6e 74 65 67 65 72 0a 2a 2a 20 77 68 69 63   integer.** whic
17a0: 68 20 69 73 20 73 74 6f 72 65 64 20 69 6e 20 74  h is stored in t
17b0: 68 65 20 6b 65 79 20 73 69 7a 65 20 65 6e 74 72  he key size entr
17c0: 79 20 6f 66 20 74 68 65 20 63 65 6c 6c 20 68 65  y of the cell he
17d0: 61 64 65 72 20 72 61 74 68 65 72 20 74 68 61 6e  ader rather than
17e0: 20 69 6e 0a 2a 2a 20 74 68 65 20 70 61 79 6c 6f   in.** the paylo
17f0: 61 64 20 61 72 65 61 2e 0a 2a 2a 0a 2a 2a 20 54  ad area..**.** T
1800: 68 65 20 63 65 6c 6c 20 70 6f 69 6e 74 65 72 20  he cell pointer 
1810: 61 72 72 61 79 20 62 65 67 69 6e 73 20 6f 6e 20  array begins on 
1820: 74 68 65 20 66 69 72 73 74 20 62 79 74 65 20 61  the first byte a
1830: 66 74 65 72 20 74 68 65 20 70 61 67 65 20 68 65  fter the page he
1840: 61 64 65 72 2e 0a 2a 2a 20 54 68 65 20 63 65 6c  ader..** The cel
1850: 6c 20 70 6f 69 6e 74 65 72 20 61 72 72 61 79 20  l pointer array 
1860: 63 6f 6e 74 61 69 6e 73 20 7a 65 72 6f 20 6f 72  contains zero or
1870: 20 6d 6f 72 65 20 32 2d 62 79 74 65 20 6e 75 6d   more 2-byte num
1880: 62 65 72 73 20 77 68 69 63 68 20 61 72 65 0a 2a  bers which are.*
1890: 2a 20 6f 66 66 73 65 74 73 20 66 72 6f 6d 20 74  * offsets from t
18a0: 68 65 20 62 65 67 69 6e 6e 69 6e 67 20 6f 66 20  he beginning of 
18b0: 74 68 65 20 70 61 67 65 20 74 6f 20 74 68 65 20  the page to the 
18c0: 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 20 69 6e 20  cell content in 
18d0: 74 68 65 20 63 65 6c 6c 0a 2a 2a 20 63 6f 6e 74  the cell.** cont
18e0: 65 6e 74 20 61 72 65 61 2e 20 20 54 68 65 20 63  ent area.  The c
18f0: 65 6c 6c 20 70 6f 69 6e 74 65 72 73 20 6f 63 63  ell pointers occ
1900: 75 72 20 69 6e 20 73 6f 72 74 65 64 20 6f 72 64  ur in sorted ord
1910: 65 72 2e 20 20 54 68 65 20 73 79 73 74 65 6d 20  er.  The system 
1920: 73 74 72 69 76 65 73 0a 2a 2a 20 74 6f 20 6b 65  strives.** to ke
1930: 65 70 20 66 72 65 65 20 73 70 61 63 65 20 61 66  ep free space af
1940: 74 65 72 20 74 68 65 20 6c 61 73 74 20 63 65 6c  ter the last cel
1950: 6c 20 70 6f 69 6e 74 65 72 20 73 6f 20 74 68 61  l pointer so tha
1960: 74 20 6e 65 77 20 63 65 6c 6c 73 20 63 61 6e 0a  t new cells can.
1970: 2a 2a 20 62 65 20 65 61 73 69 6c 79 20 61 64 64  ** be easily add
1980: 65 64 20 77 69 74 68 6f 75 74 20 68 61 76 69 6e  ed without havin
1990: 67 20 74 6f 20 64 65 66 72 61 67 6d 65 6e 74 20  g to defragment 
19a0: 74 68 65 20 70 61 67 65 2e 0a 2a 2a 0a 2a 2a 20  the page..**.** 
19b0: 43 65 6c 6c 20 63 6f 6e 74 65 6e 74 20 69 73 20  Cell content is 
19c0: 73 74 6f 72 65 64 20 61 74 20 74 68 65 20 76 65  stored at the ve
19d0: 72 79 20 65 6e 64 20 6f 66 20 74 68 65 20 70 61  ry end of the pa
19e0: 67 65 20 61 6e 64 20 67 72 6f 77 73 20 74 6f 77  ge and grows tow
19f0: 61 72 64 20 74 68 65 0a 2a 2a 20 62 65 67 69 6e  ard the.** begin
1a00: 6e 69 6e 67 20 6f 66 20 74 68 65 20 70 61 67 65  ning of the page
1a10: 2e 0a 2a 2a 0a 2a 2a 20 55 6e 75 73 65 64 20 73  ..**.** Unused s
1a20: 70 61 63 65 20 77 69 74 68 69 6e 20 74 68 65 20  pace within the 
1a30: 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 20 61 72 65  cell content are
1a40: 61 20 69 73 20 63 6f 6c 6c 65 63 74 65 64 20 69  a is collected i
1a50: 6e 74 6f 20 61 20 6c 69 6e 6b 65 64 20 6c 69 73  nto a linked lis
1a60: 74 20 6f 66 0a 2a 2a 20 66 72 65 65 62 6c 6f 63  t of.** freebloc
1a70: 6b 73 2e 20 20 45 61 63 68 20 66 72 65 65 62 6c  ks.  Each freebl
1a80: 6f 63 6b 20 69 73 20 61 74 20 6c 65 61 73 74 20  ock is at least 
1a90: 34 20 62 79 74 65 73 20 69 6e 20 73 69 7a 65 2e  4 bytes in size.
1aa0: 20 20 54 68 65 20 62 79 74 65 20 6f 66 66 73 65    The byte offse
1ab0: 74 0a 2a 2a 20 74 6f 20 74 68 65 20 66 69 72 73  t.** to the firs
1ac0: 74 20 66 72 65 65 62 6c 6f 63 6b 20 69 73 20 67  t freeblock is g
1ad0: 69 76 65 6e 20 69 6e 20 74 68 65 20 68 65 61 64  iven in the head
1ae0: 65 72 2e 20 20 46 72 65 65 62 6c 6f 63 6b 73 20  er.  Freeblocks 
1af0: 6f 63 63 75 72 20 69 6e 0a 2a 2a 20 69 6e 63 72  occur in.** incr
1b00: 65 61 73 69 6e 67 20 6f 72 64 65 72 2e 20 20 42  easing order.  B
1b10: 65 63 61 75 73 65 20 61 20 66 72 65 65 62 6c 6f  ecause a freeblo
1b20: 63 6b 20 6d 75 73 74 20 62 65 20 61 74 20 6c 65  ck must be at le
1b30: 61 73 74 20 34 20 62 79 74 65 73 20 69 6e 20 73  ast 4 bytes in s
1b40: 69 7a 65 2c 0a 2a 2a 20 61 6e 79 20 67 72 6f 75  ize,.** any grou
1b50: 70 20 6f 66 20 33 20 6f 72 20 66 65 77 65 72 20  p of 3 or fewer 
1b60: 75 6e 75 73 65 64 20 62 79 74 65 73 20 69 6e 20  unused bytes in 
1b70: 74 68 65 20 63 65 6c 6c 20 63 6f 6e 74 65 6e 74  the cell content
1b80: 20 61 72 65 61 20 63 61 6e 6e 6f 74 0a 2a 2a 20   area cannot.** 
1b90: 65 78 69 73 74 20 6f 6e 20 74 68 65 20 66 72 65  exist on the fre
1ba0: 65 62 6c 6f 63 6b 20 63 68 61 69 6e 2e 20 20 41  eblock chain.  A
1bb0: 20 67 72 6f 75 70 20 6f 66 20 33 20 6f 72 20 66   group of 3 or f
1bc0: 65 77 65 72 20 66 72 65 65 20 62 79 74 65 73 20  ewer free bytes 
1bd0: 69 73 20 63 61 6c 6c 65 64 0a 2a 2a 20 61 20 66  is called.** a f
1be0: 72 61 67 6d 65 6e 74 2e 20 20 54 68 65 20 74 6f  ragment.  The to
1bf0: 74 61 6c 20 6e 75 6d 62 65 72 20 6f 66 20 62 79  tal number of by
1c00: 74 65 73 20 69 6e 20 61 6c 6c 20 66 72 61 67 6d  tes in all fragm
1c10: 65 6e 74 73 20 69 73 20 72 65 63 6f 72 64 65 64  ents is recorded
1c20: 2e 0a 2a 2a 20 69 6e 20 74 68 65 20 70 61 67 65  ..** in the page
1c30: 20 68 65 61 64 65 72 20 61 74 20 6f 66 66 73 65   header at offse
1c40: 74 20 37 2e 0a 2a 2a 0a 2a 2a 20 20 20 20 53 49  t 7..**.**    SI
1c50: 5a 45 20 20 20 20 44 45 53 43 52 49 50 54 49 4f  ZE    DESCRIPTIO
1c60: 4e 0a 2a 2a 20 20 20 20 20 20 32 20 20 20 20 20  N.**      2     
1c70: 42 79 74 65 20 6f 66 66 73 65 74 20 6f 66 20 74  Byte offset of t
1c80: 68 65 20 6e 65 78 74 20 66 72 65 65 62 6c 6f 63  he next freebloc
1c90: 6b 0a 2a 2a 20 20 20 20 20 20 32 20 20 20 20 20  k.**      2     
1ca0: 42 79 74 65 73 20 69 6e 20 74 68 69 73 20 66 72  Bytes in this fr
1cb0: 65 65 62 6c 6f 63 6b 0a 2a 2a 0a 2a 2a 20 43 65  eeblock.**.** Ce
1cc0: 6c 6c 73 20 61 72 65 20 6f 66 20 76 61 72 69 61  lls are of varia
1cd0: 62 6c 65 20 6c 65 6e 67 74 68 2e 20 20 43 65 6c  ble length.  Cel
1ce0: 6c 73 20 61 72 65 20 73 74 6f 72 65 64 20 69 6e  ls are stored in
1cf0: 20 74 68 65 20 63 65 6c 6c 20 63 6f 6e 74 65 6e   the cell conten
1d00: 74 20 61 72 65 61 20 61 74 0a 2a 2a 20 74 68 65  t area at.** the
1d10: 20 65 6e 64 20 6f 66 20 74 68 65 20 70 61 67 65   end of the page
1d20: 2e 20 20 50 6f 69 6e 74 65 72 73 20 74 6f 20 74  .  Pointers to t
1d30: 68 65 20 63 65 6c 6c 73 20 61 72 65 20 69 6e 20  he cells are in 
1d40: 74 68 65 20 63 65 6c 6c 20 70 6f 69 6e 74 65 72  the cell pointer
1d50: 20 61 72 72 61 79 0a 2a 2a 20 74 68 61 74 20 69   array.** that i
1d60: 6d 6d 65 64 69 61 74 65 6c 79 20 66 6f 6c 6c 6f  mmediately follo
1d70: 77 73 20 74 68 65 20 70 61 67 65 20 68 65 61 64  ws the page head
1d80: 65 72 2e 20 20 43 65 6c 6c 73 20 69 73 20 6e 6f  er.  Cells is no
1d90: 74 20 6e 65 63 65 73 73 61 72 69 6c 79 0a 2a 2a  t necessarily.**
1da0: 20 63 6f 6e 74 69 67 75 6f 75 73 20 6f 72 20 69   contiguous or i
1db0: 6e 20 6f 72 64 65 72 2c 20 62 75 74 20 63 65 6c  n order, but cel
1dc0: 6c 20 70 6f 69 6e 74 65 72 73 20 61 72 65 20 63  l pointers are c
1dd0: 6f 6e 74 69 67 75 6f 75 73 20 61 6e 64 20 69 6e  ontiguous and in
1de0: 20 6f 72 64 65 72 2e 0a 2a 2a 0a 2a 2a 20 43 65   order..**.** Ce
1df0: 6c 6c 20 63 6f 6e 74 65 6e 74 20 6d 61 6b 65 73  ll content makes
1e00: 20 75 73 65 20 6f 66 20 76 61 72 69 61 62 6c 65   use of variable
1e10: 20 6c 65 6e 67 74 68 20 69 6e 74 65 67 65 72 73   length integers
1e20: 2e 20 20 41 20 76 61 72 69 61 62 6c 65 0a 2a 2a  .  A variable.**
1e30: 20 6c 65 6e 67 74 68 20 69 6e 74 65 67 65 72 20   length integer 
1e40: 69 73 20 31 20 74 6f 20 39 20 62 79 74 65 73 20  is 1 to 9 bytes 
1e50: 77 68 65 72 65 20 74 68 65 20 6c 6f 77 65 72 20  where the lower 
1e60: 37 20 62 69 74 73 20 6f 66 20 65 61 63 68 20 0a  7 bits of each .
1e70: 2a 2a 20 62 79 74 65 20 61 72 65 20 75 73 65 64  ** byte are used
1e80: 2e 20 20 54 68 65 20 69 6e 74 65 67 65 72 20 63  .  The integer c
1e90: 6f 6e 73 69 73 74 73 20 6f 66 20 61 6c 6c 20 62  onsists of all b
1ea0: 79 74 65 73 20 74 68 61 74 20 68 61 76 65 20 62  ytes that have b
1eb0: 69 74 20 38 20 73 65 74 20 61 6e 64 0a 2a 2a 20  it 8 set and.** 
1ec0: 74 68 65 20 66 69 72 73 74 20 62 79 74 65 20 77  the first byte w
1ed0: 69 74 68 20 62 69 74 20 38 20 63 6c 65 61 72 2e  ith bit 8 clear.
1ee0: 20 20 54 68 65 20 6d 6f 73 74 20 73 69 67 6e 69    The most signi
1ef0: 66 69 63 61 6e 74 20 62 79 74 65 20 6f 66 20 74  ficant byte of t
1f00: 68 65 20 69 6e 74 65 67 65 72 0a 2a 2a 20 61 70  he integer.** ap
1f10: 70 65 61 72 73 20 66 69 72 73 74 2e 20 20 41 20  pears first.  A 
1f20: 76 61 72 69 61 62 6c 65 2d 6c 65 6e 67 74 68 20  variable-length 
1f30: 69 6e 74 65 67 65 72 20 6d 61 79 20 6e 6f 74 20  integer may not 
1f40: 62 65 20 6d 6f 72 65 20 74 68 61 6e 20 39 20 62  be more than 9 b
1f50: 79 74 65 73 20 6c 6f 6e 67 2e 0a 2a 2a 20 41 73  ytes long..** As
1f60: 20 61 20 73 70 65 63 69 61 6c 20 63 61 73 65 2c   a special case,
1f70: 20 61 6c 6c 20 38 20 62 79 74 65 73 20 6f 66 20   all 8 bytes of 
1f80: 74 68 65 20 39 74 68 20 62 79 74 65 20 61 72 65  the 9th byte are
1f90: 20 75 73 65 64 20 61 73 20 64 61 74 61 2e 20 20   used as data.  
1fa0: 54 68 69 73 0a 2a 2a 20 61 6c 6c 6f 77 73 20 61  This.** allows a
1fb0: 20 36 34 2d 62 69 74 20 69 6e 74 65 67 65 72 20   64-bit integer 
1fc0: 74 6f 20 62 65 20 65 6e 63 6f 64 65 64 20 69 6e  to be encoded in
1fd0: 20 39 20 62 79 74 65 73 2e 0a 2a 2a 0a 2a 2a 20   9 bytes..**.** 
1fe0: 20 20 20 30 78 30 30 20 20 20 20 20 20 20 20 20     0x00         
1ff0: 20 20 20 20 20 20 20 20 20 20 20 20 20 62 65 63               bec
2000: 6f 6d 65 73 20 20 30 78 30 30 30 30 30 30 30 30  omes  0x00000000
2010: 0a 2a 2a 20 20 20 20 30 78 37 66 20 20 20 20 20  .**    0x7f     
2020: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2030: 20 62 65 63 6f 6d 65 73 20 20 30 78 30 30 30 30   becomes  0x0000
2040: 30 30 37 66 0a 2a 2a 20 20 20 20 30 78 38 31 20  007f.**    0x81 
2050: 30 78 30 30 20 20 20 20 20 20 20 20 20 20 20 20  0x00            
2060: 20 20 20 20 20 62 65 63 6f 6d 65 73 20 20 30 78       becomes  0x
2070: 30 30 30 30 30 30 38 30 0a 2a 2a 20 20 20 20 30  00000080.**    0
2080: 78 38 32 20 30 78 30 30 20 20 20 20 20 20 20 20  x82 0x00        
2090: 20 20 20 20 20 20 20 20 20 62 65 63 6f 6d 65 73           becomes
20a0: 20 20 30 78 30 30 30 30 30 31 30 30 0a 2a 2a 20    0x00000100.** 
20b0: 20 20 20 30 78 38 30 20 30 78 37 66 20 20 20 20     0x80 0x7f    
20c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 62 65 63               bec
20d0: 6f 6d 65 73 20 20 30 78 30 30 30 30 30 30 37 66  omes  0x0000007f
20e0: 0a 2a 2a 20 20 20 20 30 78 38 61 20 30 78 39 31  .**    0x8a 0x91
20f0: 20 30 78 64 31 20 30 78 61 63 20 30 78 37 38 20   0xd1 0xac 0x78 
2100: 20 62 65 63 6f 6d 65 73 20 20 30 78 31 32 33 34   becomes  0x1234
2110: 35 36 37 38 0a 2a 2a 20 20 20 20 30 78 38 31 20  5678.**    0x81 
2120: 30 78 38 31 20 30 78 38 31 20 30 78 38 31 20 30  0x81 0x81 0x81 0
2130: 78 30 31 20 20 62 65 63 6f 6d 65 73 20 20 30 78  x01  becomes  0x
2140: 31 30 32 30 34 30 38 31 0a 2a 2a 0a 2a 2a 20 56  10204081.**.** V
2150: 61 72 69 61 62 6c 65 20 6c 65 6e 67 74 68 20 69  ariable length i
2160: 6e 74 65 67 65 72 73 20 61 72 65 20 75 73 65 64  ntegers are used
2170: 20 66 6f 72 20 72 6f 77 69 64 73 20 61 6e 64 20   for rowids and 
2180: 74 6f 20 68 6f 6c 64 20 74 68 65 20 6e 75 6d 62  to hold the numb
2190: 65 72 20 6f 66 0a 2a 2a 20 62 79 74 65 73 20 6f  er of.** bytes o
21a0: 66 20 6b 65 79 20 61 6e 64 20 64 61 74 61 20 69  f key and data i
21b0: 6e 20 61 20 62 74 72 65 65 20 63 65 6c 6c 2e 0a  n a btree cell..
21c0: 2a 2a 0a 2a 2a 20 54 68 65 20 63 6f 6e 74 65 6e  **.** The conten
21d0: 74 20 6f 66 20 61 20 63 65 6c 6c 20 6c 6f 6f 6b  t of a cell look
21e0: 73 20 6c 69 6b 65 20 74 68 69 73 3a 0a 2a 2a 0a  s like this:.**.
21f0: 2a 2a 20 20 20 20 53 49 5a 45 20 20 20 20 44 45  **    SIZE    DE
2200: 53 43 52 49 50 54 49 4f 4e 0a 2a 2a 20 20 20 20  SCRIPTION.**    
2210: 20 20 34 20 20 20 20 20 50 61 67 65 20 6e 75 6d    4     Page num
2220: 62 65 72 20 6f 66 20 74 68 65 20 6c 65 66 74 20  ber of the left 
2230: 63 68 69 6c 64 2e 20 4f 6d 69 74 74 65 64 20 69  child. Omitted i
2240: 66 20 6c 65 61 66 20 66 6c 61 67 20 69 73 20 73  f leaf flag is s
2250: 65 74 2e 0a 2a 2a 20 20 20 20 20 76 61 72 20 20  et..**     var  
2260: 20 20 4e 75 6d 62 65 72 20 6f 66 20 62 79 74 65    Number of byte
2270: 73 20 6f 66 20 64 61 74 61 2e 20 4f 6d 69 74 74  s of data. Omitt
2280: 65 64 20 69 66 20 74 68 65 20 7a 65 72 6f 64 61  ed if the zeroda
2290: 74 61 20 66 6c 61 67 20 69 73 20 73 65 74 2e 0a  ta flag is set..
22a0: 2a 2a 20 20 20 20 20 76 61 72 20 20 20 20 4e 75  **     var    Nu
22b0: 6d 62 65 72 20 6f 66 20 62 79 74 65 73 20 6f 66  mber of bytes of
22c0: 20 6b 65 79 2e 20 4f 72 20 74 68 65 20 6b 65 79   key. Or the key
22d0: 20 69 74 73 65 6c 66 20 69 66 20 69 6e 74 6b 65   itself if intke
22e0: 79 20 66 6c 61 67 20 69 73 20 73 65 74 2e 0a 2a  y flag is set..*
22f0: 2a 20 20 20 20 20 20 2a 20 20 20 20 20 50 61 79  *      *     Pay
2300: 6c 6f 61 64 0a 2a 2a 20 20 20 20 20 20 34 20 20  load.**      4  
2310: 20 20 20 46 69 72 73 74 20 70 61 67 65 20 6f 66     First page of
2320: 20 74 68 65 20 6f 76 65 72 66 6c 6f 77 20 63 68   the overflow ch
2330: 61 69 6e 2e 20 20 4f 6d 69 74 74 65 64 20 69 66  ain.  Omitted if
2340: 20 6e 6f 20 6f 76 65 72 66 6c 6f 77 0a 2a 2a 0a   no overflow.**.
2350: 2a 2a 20 4f 76 65 72 66 6c 6f 77 20 70 61 67 65  ** Overflow page
2360: 73 20 66 6f 72 6d 20 61 20 6c 69 6e 6b 65 64 20  s form a linked 
2370: 6c 69 73 74 2e 20 20 45 61 63 68 20 70 61 67 65  list.  Each page
2380: 20 65 78 63 65 70 74 20 74 68 65 20 6c 61 73 74   except the last
2390: 20 69 73 20 63 6f 6d 70 6c 65 74 65 6c 79 0a 2a   is completely.*
23a0: 2a 20 66 69 6c 6c 65 64 20 77 69 74 68 20 64 61  * filled with da
23b0: 74 61 20 28 70 61 67 65 73 69 7a 65 20 2d 20 34  ta (pagesize - 4
23c0: 20 62 79 74 65 73 29 2e 20 20 54 68 65 20 6c 61   bytes).  The la
23d0: 73 74 20 70 61 67 65 20 63 61 6e 20 68 61 76 65  st page can have
23e0: 20 61 73 20 6c 69 74 74 6c 65 0a 2a 2a 20 61 73   as little.** as
23f0: 20 31 20 62 79 74 65 20 6f 66 20 64 61 74 61 2e   1 byte of data.
2400: 0a 2a 2a 0a 2a 2a 20 20 20 20 53 49 5a 45 20 20  .**.**    SIZE  
2410: 20 20 44 45 53 43 52 49 50 54 49 4f 4e 0a 2a 2a    DESCRIPTION.**
2420: 20 20 20 20 20 20 34 20 20 20 20 20 50 61 67 65        4     Page
2430: 20 6e 75 6d 62 65 72 20 6f 66 20 6e 65 78 74 20   number of next 
2440: 6f 76 65 72 66 6c 6f 77 20 70 61 67 65 0a 2a 2a  overflow page.**
2450: 20 20 20 20 20 20 2a 20 20 20 20 20 44 61 74 61        *     Data
2460: 0a 2a 2a 0a 2a 2a 20 46 72 65 65 6c 69 73 74 20  .**.** Freelist 
2470: 70 61 67 65 73 20 63 6f 6d 65 20 69 6e 20 74 77  pages come in tw
2480: 6f 20 73 75 62 74 79 70 65 73 3a 20 74 72 75 6e  o subtypes: trun
2490: 6b 20 70 61 67 65 73 20 61 6e 64 20 6c 65 61 66  k pages and leaf
24a0: 20 70 61 67 65 73 2e 20 20 54 68 65 0a 2a 2a 20   pages.  The.** 
24b0: 66 69 6c 65 20 68 65 61 64 65 72 20 70 6f 69 6e  file header poin
24c0: 74 73 20 74 6f 20 74 68 65 20 66 69 72 73 74 20  ts to the first 
24d0: 69 6e 20 61 20 6c 69 6e 6b 65 64 20 6c 69 73 74  in a linked list
24e0: 20 6f 66 20 74 72 75 6e 6b 20 70 61 67 65 2e 20   of trunk page. 
24f0: 20 45 61 63 68 20 74 72 75 6e 6b 0a 2a 2a 20 70   Each trunk.** p
2500: 61 67 65 20 70 6f 69 6e 74 73 20 74 6f 20 6d 75  age points to mu
2510: 6c 74 69 70 6c 65 20 6c 65 61 66 20 70 61 67 65  ltiple leaf page
2520: 73 2e 20 20 54 68 65 20 63 6f 6e 74 65 6e 74 20  s.  The content 
2530: 6f 66 20 61 20 6c 65 61 66 20 70 61 67 65 20 69  of a leaf page i
2540: 73 0a 2a 2a 20 75 6e 73 70 65 63 69 66 69 65 64  s.** unspecified
2550: 2e 20 20 41 20 74 72 75 6e 6b 20 70 61 67 65 20  .  A trunk page 
2560: 6c 6f 6f 6b 73 20 6c 69 6b 65 20 74 68 69 73 3a  looks like this:
2570: 0a 2a 2a 0a 2a 2a 20 20 20 20 53 49 5a 45 20 20  .**.**    SIZE  
2580: 20 20 44 45 53 43 52 49 50 54 49 4f 4e 0a 2a 2a    DESCRIPTION.**
2590: 20 20 20 20 20 20 34 20 20 20 20 20 50 61 67 65        4     Page
25a0: 20 6e 75 6d 62 65 72 20 6f 66 20 6e 65 78 74 20   number of next 
25b0: 74 72 75 6e 6b 20 70 61 67 65 0a 2a 2a 20 20 20  trunk page.**   
25c0: 20 20 20 34 20 20 20 20 20 4e 75 6d 62 65 72 20     4     Number 
25d0: 6f 66 20 6c 65 61 66 20 70 6f 69 6e 74 65 72 73  of leaf pointers
25e0: 20 6f 6e 20 74 68 69 73 20 70 61 67 65 0a 2a 2a   on this page.**
25f0: 20 20 20 20 20 20 2a 20 20 20 20 20 7a 65 72 6f        *     zero
2600: 20 6f 72 20 6d 6f 72 65 20 70 61 67 65 73 20 6e   or more pages n
2610: 75 6d 62 65 72 73 20 6f 66 20 6c 65 61 76 65 73  umbers of leaves
2620: 0a 2a 2f 0a 23 69 6e 63 6c 75 64 65 20 22 73 71  .*/.#include "sq
2630: 6c 69 74 65 49 6e 74 2e 68 22 0a 23 69 6e 63 6c  liteInt.h".#incl
2640: 75 64 65 20 22 70 61 67 65 72 2e 68 22 0a 23 69  ude "pager.h".#i
2650: 6e 63 6c 75 64 65 20 22 62 74 72 65 65 2e 68 22  nclude "btree.h"
2660: 0a 23 69 6e 63 6c 75 64 65 20 22 6f 73 2e 68 22  .#include "os.h"
2670: 0a 23 69 6e 63 6c 75 64 65 20 3c 61 73 73 65 72  .#include <asser
2680: 74 2e 68 3e 0a 0a 2f 2a 20 52 6f 75 6e 64 20 75  t.h>../* Round u
2690: 70 20 61 20 6e 75 6d 62 65 72 20 74 6f 20 74 68  p a number to th
26a0: 65 20 6e 65 78 74 20 6c 61 72 67 65 72 20 6d 75  e next larger mu
26b0: 6c 74 69 70 6c 65 20 6f 66 20 38 2e 20 20 54 68  ltiple of 8.  Th
26c0: 69 73 20 69 73 20 75 73 65 64 0a 2a 2a 20 74 6f  is is used.** to
26d0: 20 66 6f 72 63 65 20 38 2d 62 79 74 65 20 61 6c   force 8-byte al
26e0: 69 67 6e 6d 65 6e 74 20 6f 6e 20 36 34 2d 62 69  ignment on 64-bi
26f0: 74 20 61 72 63 68 69 74 65 63 74 75 72 65 73 2e  t architectures.
2700: 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 52 4f 55 4e  .*/.#define ROUN
2710: 44 38 28 78 29 20 20 20 28 28 78 2b 37 29 26 7e  D8(x)   ((x+7)&~
2720: 37 29 0a 0a 0a 2f 2a 20 54 68 65 20 66 6f 6c 6c  7).../* The foll
2730: 6f 77 69 6e 67 20 76 61 6c 75 65 20 69 73 20 74  owing value is t
2740: 68 65 20 6d 61 78 69 6d 75 6d 20 63 65 6c 6c 20  he maximum cell 
2750: 73 69 7a 65 20 61 73 73 75 6d 69 6e 67 20 61 20  size assuming a 
2760: 6d 61 78 69 6d 75 6d 20 70 61 67 65 0a 2a 2a 20  maximum page.** 
2770: 73 69 7a 65 20 67 69 76 65 20 61 62 6f 76 65 2e  size give above.
2780: 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 4d 58 5f 43  .*/.#define MX_C
2790: 45 4c 4c 5f 53 49 5a 45 28 70 42 74 29 20 20 28  ELL_SIZE(pBt)  (
27a0: 70 42 74 2d 3e 70 61 67 65 53 69 7a 65 2d 38 29  pBt->pageSize-8)
27b0: 0a 0a 2f 2a 20 54 68 65 20 6d 61 78 69 6d 75 6d  ../* The maximum
27c0: 20 6e 75 6d 62 65 72 20 6f 66 20 63 65 6c 6c 73   number of cells
27d0: 20 6f 6e 20 61 20 73 69 6e 67 6c 65 20 70 61 67   on a single pag
27e0: 65 20 6f 66 20 74 68 65 20 64 61 74 61 62 61 73  e of the databas
27f0: 65 2e 20 20 54 68 69 73 0a 2a 2a 20 61 73 73 75  e.  This.** assu
2800: 6d 65 73 20 61 20 6d 69 6e 69 6d 75 6d 20 63 65  mes a minimum ce
2810: 6c 6c 20 73 69 7a 65 20 6f 66 20 33 20 62 79 74  ll size of 3 byt
2820: 65 73 2e 20 20 53 75 63 68 20 73 6d 61 6c 6c 20  es.  Such small 
2830: 63 65 6c 6c 73 20 77 69 6c 6c 20 62 65 0a 2a 2a  cells will be.**
2840: 20 65 78 63 65 65 64 69 6e 67 6c 79 20 72 61 72   exceedingly rar
2850: 65 2c 20 62 75 74 20 74 68 65 79 20 61 72 65 20  e, but they are 
2860: 70 6f 73 73 69 62 6c 65 2e 0a 2a 2f 0a 23 64 65  possible..*/.#de
2870: 66 69 6e 65 20 4d 58 5f 43 45 4c 4c 28 70 42 74  fine MX_CELL(pBt
2880: 29 20 28 28 70 42 74 2d 3e 70 61 67 65 53 69 7a  ) ((pBt->pageSiz
2890: 65 2d 38 29 2f 33 29 0a 0a 2f 2a 20 46 6f 72 77  e-8)/3)../* Forw
28a0: 61 72 64 20 64 65 63 6c 61 72 61 74 69 6f 6e 73  ard declarations
28b0: 20 2a 2f 0a 74 79 70 65 64 65 66 20 73 74 72 75   */.typedef stru
28c0: 63 74 20 4d 65 6d 50 61 67 65 20 4d 65 6d 50 61  ct MemPage MemPa
28d0: 67 65 3b 0a 74 79 70 65 64 65 66 20 73 74 72 75  ge;.typedef stru
28e0: 63 74 20 42 74 4c 6f 63 6b 20 42 74 4c 6f 63 6b  ct BtLock BtLock
28f0: 3b 0a 0a 2f 2a 0a 2a 2a 20 54 68 69 73 20 69 73  ;../*.** This is
2900: 20 61 20 6d 61 67 69 63 20 73 74 72 69 6e 67 20   a magic string 
2910: 74 68 61 74 20 61 70 70 65 61 72 73 20 61 74 20  that appears at 
2920: 74 68 65 20 62 65 67 69 6e 6e 69 6e 67 20 6f 66  the beginning of
2930: 20 65 76 65 72 79 0a 2a 2a 20 53 51 4c 69 74 65   every.** SQLite
2940: 20 64 61 74 61 62 61 73 65 20 69 6e 20 6f 72 64   database in ord
2950: 65 72 20 74 6f 20 69 64 65 6e 74 69 66 79 20 74  er to identify t
2960: 68 65 20 66 69 6c 65 20 61 73 20 61 20 72 65 61  he file as a rea
2970: 6c 20 64 61 74 61 62 61 73 65 2e 0a 2a 2a 0a 2a  l database..**.*
2980: 2a 20 59 6f 75 20 63 61 6e 20 63 68 61 6e 67 65  * You can change
2990: 20 74 68 69 73 20 76 61 6c 75 65 20 61 74 20 63   this value at c
29a0: 6f 6d 70 69 6c 65 2d 74 69 6d 65 20 62 79 20 73  ompile-time by s
29b0: 70 65 63 69 66 79 69 6e 67 20 61 0a 2a 2a 20 2d  pecifying a.** -
29c0: 44 53 51 4c 49 54 45 5f 46 49 4c 45 5f 48 45 41  DSQLITE_FILE_HEA
29d0: 44 45 52 3d 22 2e 2e 2e 22 20 6f 6e 20 74 68 65  DER="..." on the
29e0: 20 63 6f 6d 70 69 6c 65 72 20 63 6f 6d 6d 61 6e   compiler comman
29f0: 64 2d 6c 69 6e 65 2e 20 20 54 68 65 0a 2a 2a 20  d-line.  The.** 
2a00: 68 65 61 64 65 72 20 6d 75 73 74 20 62 65 20 65  header must be e
2a10: 78 61 63 74 6c 79 20 31 36 20 62 79 74 65 73 20  xactly 16 bytes 
2a20: 69 6e 63 6c 75 64 69 6e 67 20 74 68 65 20 7a 65  including the ze
2a30: 72 6f 2d 74 65 72 6d 69 6e 61 74 6f 72 20 73 6f  ro-terminator so
2a40: 0a 2a 2a 20 74 68 65 20 73 74 72 69 6e 67 20 69  .** the string i
2a50: 74 73 65 6c 66 20 73 68 6f 75 6c 64 20 62 65 20  tself should be 
2a60: 31 35 20 63 68 61 72 61 63 74 65 72 73 20 6c 6f  15 characters lo
2a70: 6e 67 2e 20 20 49 66 20 79 6f 75 20 63 68 61 6e  ng.  If you chan
2a80: 67 65 0a 2a 2a 20 74 68 65 20 68 65 61 64 65 72  ge.** the header
2a90: 2c 20 74 68 65 6e 20 79 6f 75 72 20 63 75 73 74  , then your cust
2aa0: 6f 6d 20 6c 69 62 72 61 72 79 20 77 69 6c 6c 20  om library will 
2ab0: 6e 6f 74 20 62 65 20 61 62 6c 65 20 74 6f 20 72  not be able to r
2ac0: 65 61 64 20 0a 2a 2a 20 64 61 74 61 62 61 73 65  ead .** database
2ad0: 73 20 67 65 6e 65 72 61 74 65 64 20 62 79 20 74  s generated by t
2ae0: 68 65 20 73 74 61 6e 64 61 72 64 20 74 6f 6f 6c  he standard tool
2af0: 73 20 61 6e 64 20 74 68 65 20 73 74 61 6e 64 61  s and the standa
2b00: 72 64 20 74 6f 6f 6c 73 0a 2a 2a 20 77 69 6c 6c  rd tools.** will
2b10: 20 6e 6f 74 20 62 65 20 61 62 6c 65 20 74 6f 20   not be able to 
2b20: 72 65 61 64 20 64 61 74 61 62 61 73 65 73 20 63  read databases c
2b30: 72 65 61 74 65 64 20 62 79 20 79 6f 75 72 20 63  reated by your c
2b40: 75 73 74 6f 6d 20 6c 69 62 72 61 72 79 2e 0a 2a  ustom library..*
2b50: 2f 0a 23 69 66 6e 64 65 66 20 53 51 4c 49 54 45  /.#ifndef SQLITE
2b60: 5f 46 49 4c 45 5f 48 45 41 44 45 52 20 2f 2a 20  _FILE_HEADER /* 
2b70: 31 32 33 34 35 36 37 38 39 20 31 32 33 34 35 36  123456789 123456
2b80: 20 2a 2f 0a 23 20 20 64 65 66 69 6e 65 20 53 51   */.#  define SQ
2b90: 4c 49 54 45 5f 46 49 4c 45 5f 48 45 41 44 45 52  LITE_FILE_HEADER
2ba0: 20 22 53 51 4c 69 74 65 20 66 6f 72 6d 61 74 20   "SQLite format 
2bb0: 33 22 0a 23 65 6e 64 69 66 0a 0a 2f 2a 0a 2a 2a  3".#endif../*.**
2bc0: 20 50 61 67 65 20 74 79 70 65 20 66 6c 61 67 73   Page type flags
2bd0: 2e 20 20 41 6e 20 4f 52 65 64 20 63 6f 6d 62 69  .  An ORed combi
2be0: 6e 61 74 69 6f 6e 20 6f 66 20 74 68 65 73 65 20  nation of these 
2bf0: 66 6c 61 67 73 20 61 70 70 65 61 72 20 61 73 20  flags appear as 
2c00: 74 68 65 0a 2a 2a 20 66 69 72 73 74 20 62 79 74  the.** first byt
2c10: 65 20 6f 66 20 6f 6e 2d 64 69 73 6b 20 69 6d 61  e of on-disk ima
2c20: 67 65 20 6f 66 20 65 76 65 72 79 20 42 54 72 65  ge of every BTre
2c30: 65 20 70 61 67 65 2e 0a 2a 2f 0a 23 64 65 66 69  e page..*/.#defi
2c40: 6e 65 20 50 54 46 5f 49 4e 54 4b 45 59 20 20 20  ne PTF_INTKEY   
2c50: 20 30 78 30 31 0a 23 64 65 66 69 6e 65 20 50 54   0x01.#define PT
2c60: 46 5f 5a 45 52 4f 44 41 54 41 20 20 30 78 30 32  F_ZERODATA  0x02
2c70: 0a 23 64 65 66 69 6e 65 20 50 54 46 5f 4c 45 41  .#define PTF_LEA
2c80: 46 44 41 54 41 20 20 30 78 30 34 0a 23 64 65 66  FDATA  0x04.#def
2c90: 69 6e 65 20 50 54 46 5f 4c 45 41 46 20 20 20 20  ine PTF_LEAF    
2ca0: 20 20 30 78 30 38 0a 0a 2f 2a 0a 2a 2a 20 41 73    0x08../*.** As
2cb0: 20 65 61 63 68 20 70 61 67 65 20 6f 66 20 74 68   each page of th
2cc0: 65 20 66 69 6c 65 20 69 73 20 6c 6f 61 64 65 64  e file is loaded
2cd0: 20 69 6e 74 6f 20 6d 65 6d 6f 72 79 2c 20 61 6e   into memory, an
2ce0: 20 69 6e 73 74 61 6e 63 65 20 6f 66 20 74 68 65   instance of the
2cf0: 20 66 6f 6c 6c 6f 77 69 6e 67 0a 2a 2a 20 73 74   following.** st
2d00: 72 75 63 74 75 72 65 20 69 73 20 61 70 70 65 6e  ructure is appen
2d10: 64 65 64 20 61 6e 64 20 69 6e 69 74 69 61 6c 69  ded and initiali
2d20: 7a 65 64 20 74 6f 20 7a 65 72 6f 2e 20 20 54 68  zed to zero.  Th
2d30: 69 73 20 73 74 72 75 63 74 75 72 65 20 73 74 6f  is structure sto
2d40: 72 65 73 0a 2a 2a 20 69 6e 66 6f 72 6d 61 74 69  res.** informati
2d50: 6f 6e 20 61 62 6f 75 74 20 74 68 65 20 70 61 67  on about the pag
2d60: 65 20 74 68 61 74 20 69 73 20 64 65 63 6f 64 65  e that is decode
2d70: 64 20 66 72 6f 6d 20 74 68 65 20 72 61 77 20 66  d from the raw f
2d80: 69 6c 65 20 70 61 67 65 2e 0a 2a 2a 0a 2a 2a 20  ile page..**.** 
2d90: 54 68 65 20 70 50 61 72 65 6e 74 20 66 69 65 6c  The pParent fiel
2da0: 64 20 70 6f 69 6e 74 73 20 62 61 63 6b 20 74 6f  d points back to
2db0: 20 74 68 65 20 70 61 72 65 6e 74 20 70 61 67 65   the parent page
2dc0: 2e 20 20 54 68 69 73 20 61 6c 6c 6f 77 73 20 75  .  This allows u
2dd0: 73 20 74 6f 0a 2a 2a 20 77 61 6c 6b 20 75 70 20  s to.** walk up 
2de0: 74 68 65 20 42 54 72 65 65 20 66 72 6f 6d 20 61  the BTree from a
2df0: 6e 79 20 6c 65 61 66 20 74 6f 20 74 68 65 20 72  ny leaf to the r
2e00: 6f 6f 74 2e 20 20 43 61 72 65 20 6d 75 73 74 20  oot.  Care must 
2e10: 62 65 20 74 61 6b 65 6e 20 74 6f 0a 2a 2a 20 75  be taken to.** u
2e20: 6e 72 65 66 28 29 20 74 68 65 20 70 61 72 65 6e  nref() the paren
2e30: 74 20 70 61 67 65 20 70 6f 69 6e 74 65 72 20 77  t page pointer w
2e40: 68 65 6e 20 74 68 69 73 20 70 61 67 65 20 69 73  hen this page is
2e50: 20 6e 6f 20 6c 6f 6e 67 65 72 20 72 65 66 65 72   no longer refer
2e60: 65 6e 63 65 64 2e 0a 2a 2a 20 54 68 65 20 70 61  enced..** The pa
2e70: 67 65 44 65 73 74 72 75 63 74 6f 72 28 29 20 72  geDestructor() r
2e80: 6f 75 74 69 6e 65 20 68 61 6e 64 6c 65 73 20 74  outine handles t
2e90: 68 61 74 20 63 68 6f 72 65 2e 0a 2a 2a 0a 2a 2a  hat chore..**.**
2ea0: 20 41 63 63 65 73 73 20 74 6f 20 61 6c 6c 20 66   Access to all f
2eb0: 69 65 6c 64 73 20 6f 66 20 74 68 69 73 20 73 74  ields of this st
2ec0: 72 75 63 74 75 72 65 20 69 73 20 63 6f 6e 74 72  ructure is contr
2ed0: 6f 6c 6c 65 64 20 62 79 20 74 68 65 20 6d 75 74  olled by the mut
2ee0: 65 78 0a 2a 2a 20 73 74 6f 72 65 64 20 69 6e 20  ex.** stored in 
2ef0: 4d 65 6d 50 61 67 65 2e 70 42 74 2d 3e 6d 75 74  MemPage.pBt->mut
2f00: 65 78 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 4d 65  ex..*/.struct Me
2f10: 6d 50 61 67 65 20 7b 0a 20 20 75 38 20 69 73 49  mPage {.  u8 isI
2f20: 6e 69 74 3b 20 20 20 20 20 20 20 20 20 20 20 2f  nit;           /
2f30: 2a 20 54 72 75 65 20 69 66 20 70 72 65 76 69 6f  * True if previo
2f40: 75 73 6c 79 20 69 6e 69 74 69 61 6c 69 7a 65 64  usly initialized
2f50: 2e 20 4d 55 53 54 20 42 45 20 46 49 52 53 54 21  . MUST BE FIRST!
2f60: 20 2a 2f 0a 20 20 75 38 20 69 64 78 53 68 69 66   */.  u8 idxShif
2f70: 74 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 54 72  t;         /* Tr
2f80: 75 65 20 69 66 20 43 65 6c 6c 20 69 6e 64 69 63  ue if Cell indic
2f90: 65 73 20 68 61 76 65 20 63 68 61 6e 67 65 64 20  es have changed 
2fa0: 2a 2f 0a 20 20 75 38 20 6e 4f 76 65 72 66 6c 6f  */.  u8 nOverflo
2fb0: 77 3b 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d  w;        /* Num
2fc0: 62 65 72 20 6f 66 20 6f 76 65 72 66 6c 6f 77 20  ber of overflow 
2fd0: 63 65 6c 6c 20 62 6f 64 69 65 73 20 69 6e 20 61  cell bodies in a
2fe0: 43 65 6c 6c 5b 5d 20 2a 2f 0a 20 20 75 38 20 69  Cell[] */.  u8 i
2ff0: 6e 74 4b 65 79 3b 20 20 20 20 20 20 20 20 20 20  ntKey;          
3000: 20 2f 2a 20 54 72 75 65 20 69 66 20 69 6e 74 6b   /* True if intk
3010: 65 79 20 66 6c 61 67 20 69 73 20 73 65 74 20 2a  ey flag is set *
3020: 2f 0a 20 20 75 38 20 6c 65 61 66 3b 20 20 20 20  /.  u8 leaf;    
3030: 20 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65           /* True
3040: 20 69 66 20 6c 65 61 66 20 66 6c 61 67 20 69 73   if leaf flag is
3050: 20 73 65 74 20 2a 2f 0a 20 20 75 38 20 7a 65 72   set */.  u8 zer
3060: 6f 44 61 74 61 3b 20 20 20 20 20 20 20 20 20 2f  oData;         /
3070: 2a 20 54 72 75 65 20 69 66 20 74 61 62 6c 65 20  * True if table 
3080: 73 74 6f 72 65 73 20 6b 65 79 73 20 6f 6e 6c 79  stores keys only
3090: 20 2a 2f 0a 20 20 75 38 20 6c 65 61 66 44 61 74   */.  u8 leafDat
30a0: 61 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 54 72  a;         /* Tr
30b0: 75 65 20 69 66 20 74 61 62 6c 65 73 20 73 74 6f  ue if tables sto
30c0: 72 65 73 20 64 61 74 61 20 6f 6e 20 6c 65 61 76  res data on leav
30d0: 65 73 20 6f 6e 6c 79 20 2a 2f 0a 20 20 75 38 20  es only */.  u8 
30e0: 68 61 73 44 61 74 61 3b 20 20 20 20 20 20 20 20  hasData;        
30f0: 20 20 2f 2a 20 54 72 75 65 20 69 66 20 74 68 69    /* True if thi
3100: 73 20 70 61 67 65 20 73 74 6f 72 65 73 20 64 61  s page stores da
3110: 74 61 20 2a 2f 0a 20 20 75 38 20 68 64 72 4f 66  ta */.  u8 hdrOf
3120: 66 73 65 74 3b 20 20 20 20 20 20 20 20 2f 2a 20  fset;        /* 
3130: 31 30 30 20 66 6f 72 20 70 61 67 65 20 31 2e 20  100 for page 1. 
3140: 20 30 20 6f 74 68 65 72 77 69 73 65 20 2a 2f 0a   0 otherwise */.
3150: 20 20 75 38 20 63 68 69 6c 64 50 74 72 53 69 7a    u8 childPtrSiz
3160: 65 3b 20 20 20 20 20 2f 2a 20 30 20 69 66 20 6c  e;     /* 0 if l
3170: 65 61 66 3d 3d 31 2e 20 20 34 20 69 66 20 6c 65  eaf==1.  4 if le
3180: 61 66 3d 3d 30 20 2a 2f 0a 20 20 75 31 36 20 6d  af==0 */.  u16 m
3190: 61 78 4c 6f 63 61 6c 3b 20 20 20 20 20 20 20 20  axLocal;        
31a0: 2f 2a 20 43 6f 70 79 20 6f 66 20 42 74 53 68 61  /* Copy of BtSha
31b0: 72 65 64 2e 6d 61 78 4c 6f 63 61 6c 20 6f 72 20  red.maxLocal or 
31c0: 42 74 53 68 61 72 65 64 2e 6d 61 78 4c 65 61 66  BtShared.maxLeaf
31d0: 20 2a 2f 0a 20 20 75 31 36 20 6d 69 6e 4c 6f 63   */.  u16 minLoc
31e0: 61 6c 3b 20 20 20 20 20 20 20 20 2f 2a 20 43 6f  al;        /* Co
31f0: 70 79 20 6f 66 20 42 74 53 68 61 72 65 64 2e 6d  py of BtShared.m
3200: 69 6e 4c 6f 63 61 6c 20 6f 72 20 42 74 53 68 61  inLocal or BtSha
3210: 72 65 64 2e 6d 69 6e 4c 65 61 66 20 2a 2f 0a 20  red.minLeaf */. 
3220: 20 75 31 36 20 63 65 6c 6c 4f 66 66 73 65 74 3b   u16 cellOffset;
3230: 20 20 20 20 20 20 2f 2a 20 49 6e 64 65 78 20 69        /* Index i
3240: 6e 20 61 44 61 74 61 20 6f 66 20 66 69 72 73 74  n aData of first
3250: 20 63 65 6c 6c 20 70 6f 69 6e 74 65 72 20 2a 2f   cell pointer */
3260: 0a 20 20 75 31 36 20 69 64 78 50 61 72 65 6e 74  .  u16 idxParent
3270: 3b 20 20 20 20 20 20 20 2f 2a 20 49 6e 64 65 78  ;       /* Index
3280: 20 69 6e 20 70 61 72 65 6e 74 20 6f 66 20 74 68   in parent of th
3290: 69 73 20 6e 6f 64 65 20 2a 2f 0a 20 20 75 31 36  is node */.  u16
32a0: 20 6e 46 72 65 65 3b 20 20 20 20 20 20 20 20 20   nFree;         
32b0: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 66    /* Number of f
32c0: 72 65 65 20 62 79 74 65 73 20 6f 6e 20 74 68 65  ree bytes on the
32d0: 20 70 61 67 65 20 2a 2f 0a 20 20 75 31 36 20 6e   page */.  u16 n
32e0: 43 65 6c 6c 3b 20 20 20 20 20 20 20 20 20 20 20  Cell;           
32f0: 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 63 65 6c  /* Number of cel
3300: 6c 73 20 6f 6e 20 74 68 69 73 20 70 61 67 65 2c  ls on this page,
3310: 20 6c 6f 63 61 6c 20 61 6e 64 20 6f 76 66 6c 20   local and ovfl 
3320: 2a 2f 0a 20 20 73 74 72 75 63 74 20 5f 4f 76 66  */.  struct _Ovf
3330: 6c 43 65 6c 6c 20 7b 20 20 20 2f 2a 20 43 65 6c  lCell {   /* Cel
3340: 6c 73 20 74 68 61 74 20 77 69 6c 6c 20 6e 6f 74  ls that will not
3350: 20 66 69 74 20 6f 6e 20 61 44 61 74 61 5b 5d 20   fit on aData[] 
3360: 2a 2f 0a 20 20 20 20 75 38 20 2a 70 43 65 6c 6c  */.    u8 *pCell
3370: 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 50 6f  ;          /* Po
3380: 69 6e 74 65 72 73 20 74 6f 20 74 68 65 20 62 6f  inters to the bo
3390: 64 79 20 6f 66 20 74 68 65 20 6f 76 65 72 66 6c  dy of the overfl
33a0: 6f 77 20 63 65 6c 6c 20 2a 2f 0a 20 20 20 20 75  ow cell */.    u
33b0: 31 36 20 69 64 78 3b 20 20 20 20 20 20 20 20 20  16 idx;         
33c0: 20 20 20 2f 2a 20 49 6e 73 65 72 74 20 74 68 69     /* Insert thi
33d0: 73 20 63 65 6c 6c 20 62 65 66 6f 72 65 20 69 64  s cell before id
33e0: 78 2d 74 68 20 6e 6f 6e 2d 6f 76 65 72 66 6c 6f  x-th non-overflo
33f0: 77 20 63 65 6c 6c 20 2a 2f 0a 20 20 7d 20 61 4f  w cell */.  } aO
3400: 76 66 6c 5b 35 5d 3b 0a 20 20 42 74 53 68 61 72  vfl[5];.  BtShar
3410: 65 64 20 2a 70 42 74 3b 20 20 20 20 20 20 20 2f  ed *pBt;       /
3420: 2a 20 50 6f 69 6e 74 65 72 20 74 6f 20 42 74 53  * Pointer to BtS
3430: 68 61 72 65 64 20 74 68 61 74 20 74 68 69 73 20  hared that this 
3440: 70 61 67 65 20 69 73 20 70 61 72 74 20 6f 66 20  page is part of 
3450: 2a 2f 0a 20 20 75 38 20 2a 61 44 61 74 61 3b 20  */.  u8 *aData; 
3460: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 50 6f 69            /* Poi
3470: 6e 74 65 72 20 74 6f 20 64 69 73 6b 20 69 6d 61  nter to disk ima
3480: 67 65 20 6f 66 20 74 68 65 20 70 61 67 65 20 64  ge of the page d
3490: 61 74 61 20 2a 2f 0a 20 20 44 62 50 61 67 65 20  ata */.  DbPage 
34a0: 2a 70 44 62 50 61 67 65 3b 20 20 20 20 20 2f 2a  *pDbPage;     /*
34b0: 20 50 61 67 65 72 20 70 61 67 65 20 68 61 6e 64   Pager page hand
34c0: 6c 65 20 2a 2f 0a 20 20 50 67 6e 6f 20 70 67 6e  le */.  Pgno pgn
34d0: 6f 3b 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20  o;           /* 
34e0: 50 61 67 65 20 6e 75 6d 62 65 72 20 66 6f 72 20  Page number for 
34f0: 74 68 69 73 20 70 61 67 65 20 2a 2f 0a 20 20 4d  this page */.  M
3500: 65 6d 50 61 67 65 20 2a 70 50 61 72 65 6e 74 3b  emPage *pParent;
3510: 20 20 20 20 2f 2a 20 54 68 65 20 70 61 72 65 6e      /* The paren
3520: 74 20 6f 66 20 74 68 69 73 20 70 61 67 65 2e 20  t of this page. 
3530: 20 4e 55 4c 4c 20 66 6f 72 20 72 6f 6f 74 20 2a   NULL for root *
3540: 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 20  /.};../*.** The 
3550: 69 6e 2d 6d 65 6d 6f 72 79 20 69 6d 61 67 65 20  in-memory image 
3560: 6f 66 20 61 20 64 69 73 6b 20 70 61 67 65 20 68  of a disk page h
3570: 61 73 20 74 68 65 20 61 75 78 69 6c 69 61 72 79  as the auxiliary
3580: 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 61 70 70   information app
3590: 65 6e 64 65 64 0a 2a 2a 20 74 6f 20 74 68 65 20  ended.** to the 
35a0: 65 6e 64 2e 20 20 45 58 54 52 41 5f 53 49 5a 45  end.  EXTRA_SIZE
35b0: 20 69 73 20 74 68 65 20 6e 75 6d 62 65 72 20 6f   is the number o
35c0: 66 20 62 79 74 65 73 20 6f 66 20 73 70 61 63 65  f bytes of space
35d0: 20 6e 65 65 64 65 64 20 74 6f 20 68 6f 6c 64 0a   needed to hold.
35e0: 2a 2a 20 74 68 61 74 20 65 78 74 72 61 20 69 6e  ** that extra in
35f0: 66 6f 72 6d 61 74 69 6f 6e 2e 0a 2a 2f 0a 23 64  formation..*/.#d
3600: 65 66 69 6e 65 20 45 58 54 52 41 5f 53 49 5a 45  efine EXTRA_SIZE
3610: 20 73 69 7a 65 6f 66 28 4d 65 6d 50 61 67 65 29   sizeof(MemPage)
3620: 0a 0a 2f 2a 20 41 20 42 74 72 65 65 20 68 61 6e  ../* A Btree han
3630: 64 6c 65 0a 2a 2a 0a 2a 2a 20 41 20 64 61 74 61  dle.**.** A data
3640: 62 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 20  base connection 
3650: 63 6f 6e 74 61 69 6e 73 20 61 20 70 6f 69 6e 74  contains a point
3660: 65 72 20 74 6f 20 61 6e 20 69 6e 73 74 61 6e 63  er to an instanc
3670: 65 20 6f 66 0a 2a 2a 20 74 68 69 73 20 6f 62 6a  e of.** this obj
3680: 65 63 74 20 66 6f 72 20 65 76 65 72 79 20 64 61  ect for every da
3690: 74 61 62 61 73 65 20 66 69 6c 65 20 74 68 61 74  tabase file that
36a0: 20 69 74 20 68 61 73 20 6f 70 65 6e 2e 20 20 54   it has open.  T
36b0: 68 69 73 20 73 74 72 75 63 74 75 72 65 0a 2a 2a  his structure.**
36c0: 20 69 73 20 6f 70 61 71 75 65 20 74 6f 20 74 68   is opaque to th
36d0: 65 20 64 61 74 61 62 61 73 65 20 63 6f 6e 6e 65  e database conne
36e0: 63 74 69 6f 6e 2e 20 20 54 68 65 20 64 61 74 61  ction.  The data
36f0: 62 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 20  base connection 
3700: 63 61 6e 6e 6f 74 0a 2a 2a 20 73 65 65 20 74 68  cannot.** see th
3710: 65 20 69 6e 74 65 72 6e 61 6c 73 20 6f 66 20 74  e internals of t
3720: 68 69 73 20 73 74 72 75 63 74 75 72 65 20 61 6e  his structure an
3730: 64 20 6f 6e 6c 79 20 64 65 61 6c 73 20 77 69 74  d only deals wit
3740: 68 20 70 6f 69 6e 74 65 72 73 20 74 6f 0a 2a 2a  h pointers to.**
3750: 20 74 68 69 73 20 73 74 72 75 63 74 75 72 65 2e   this structure.
3760: 0a 2a 2a 0a 2a 2a 20 46 6f 72 20 73 6f 6d 65 20  .**.** For some 
3770: 64 61 74 61 62 61 73 65 20 66 69 6c 65 73 2c 20  database files, 
3780: 74 68 65 20 73 61 6d 65 20 75 6e 64 65 72 6c 79  the same underly
3790: 69 6e 67 20 64 61 74 61 62 61 73 65 20 63 61 63  ing database cac
37a0: 68 65 20 6d 69 67 68 74 20 62 65 20 0a 2a 2a 20  he might be .** 
37b0: 73 68 61 72 65 64 20 62 65 74 77 65 65 6e 20 6d  shared between m
37c0: 75 6c 74 69 70 6c 65 20 63 6f 6e 6e 65 63 74 69  ultiple connecti
37d0: 6f 6e 73 2e 20 20 49 6e 20 74 68 61 74 20 63 61  ons.  In that ca
37e0: 73 65 2c 20 65 61 63 68 20 63 6f 6e 74 65 63 74  se, each contect
37f0: 69 6f 6e 0a 2a 2a 20 68 61 73 20 69 74 20 6f 77  ion.** has it ow
3800: 6e 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 69  n pointer to thi
3810: 73 20 6f 62 6a 65 63 74 2e 20 20 42 75 74 20 65  s object.  But e
3820: 61 63 68 20 69 6e 73 74 61 6e 63 65 20 6f 66 20  ach instance of 
3830: 74 68 69 73 20 6f 62 6a 65 63 74 0a 2a 2a 20 70  this object.** p
3840: 6f 69 6e 74 73 20 74 6f 20 74 68 65 20 73 61 6d  oints to the sam
3850: 65 20 42 74 53 68 61 72 65 64 20 6f 62 6a 65 63  e BtShared objec
3860: 74 2e 20 20 54 68 65 20 64 61 74 61 62 61 73 65  t.  The database
3870: 20 63 61 63 68 65 20 61 6e 64 20 74 68 65 0a 2a   cache and the.*
3880: 2a 20 73 63 68 65 6d 61 20 61 73 73 6f 63 69 61  * schema associa
3890: 74 65 64 20 77 69 74 68 20 74 68 65 20 64 61 74  ted with the dat
38a0: 61 62 61 73 65 20 66 69 6c 65 20 61 72 65 20 61  abase file are a
38b0: 6c 6c 20 63 6f 6e 74 61 69 6e 65 64 20 77 69 74  ll contained wit
38c0: 68 69 6e 0a 2a 2a 20 74 68 65 20 42 74 53 68 61  hin.** the BtSha
38d0: 72 65 64 20 6f 62 6a 65 63 74 2e 0a 2a 2a 0a 2a  red object..**.*
38e0: 2a 20 41 6c 6c 20 66 69 65 6c 64 73 20 69 6e 20  * All fields in 
38f0: 74 68 69 73 20 73 74 72 75 63 74 75 72 65 20 61  this structure a
3900: 72 65 20 61 63 63 65 73 73 65 64 20 75 6e 64 65  re accessed unde
3910: 72 20 73 71 6c 69 74 65 33 2e 6d 75 74 65 78 2e  r sqlite3.mutex.
3920: 0a 2a 2a 20 54 68 65 20 70 42 74 20 70 6f 69 6e  .** The pBt poin
3930: 74 65 72 20 69 74 73 65 6c 66 20 6d 61 79 20 6e  ter itself may n
3940: 6f 74 20 62 65 20 63 68 61 6e 67 65 64 20 77 68  ot be changed wh
3950: 69 6c 65 20 74 68 65 72 65 20 65 78 69 73 74 73  ile there exists
3960: 20 63 75 72 73 6f 72 73 20 0a 2a 2a 20 69 6e 20   cursors .** in 
3970: 74 68 65 20 72 65 66 65 72 65 6e 63 65 64 20 42  the referenced B
3980: 74 53 68 61 72 65 64 20 74 68 61 74 20 70 6f 69  tShared that poi
3990: 6e 74 20 62 61 63 6b 20 74 6f 20 74 68 69 73 20  nt back to this 
39a0: 42 74 72 65 65 20 73 69 6e 63 65 20 74 68 6f 73  Btree since thos
39b0: 65 0a 2a 2a 20 63 75 72 73 6f 72 73 20 68 61 76  e.** cursors hav
39c0: 65 20 74 6f 20 64 6f 20 67 6f 20 74 68 72 6f 75  e to do go throu
39d0: 67 68 20 74 68 69 73 20 42 74 72 65 65 20 74 6f  gh this Btree to
39e0: 20 66 69 6e 64 20 74 68 65 69 72 20 42 74 53 68   find their BtSh
39f0: 61 72 65 64 20 61 6e 64 0a 2a 2a 20 74 68 65 79  ared and.** they
3a00: 20 6f 66 74 65 6e 20 64 6f 20 73 6f 20 77 69 74   often do so wit
3a10: 68 6f 75 74 20 68 6f 6c 64 69 6e 67 20 73 71 6c  hout holding sql
3a20: 69 74 65 33 2e 6d 75 74 65 78 2e 0a 2a 2f 0a 73  ite3.mutex..*/.s
3a30: 74 72 75 63 74 20 42 74 72 65 65 20 7b 0a 20 20  truct Btree {.  
3a40: 73 71 6c 69 74 65 33 20 2a 70 53 71 6c 69 74 65  sqlite3 *pSqlite
3a50: 3b 20 20 2f 2a 20 54 68 65 20 64 61 74 61 62 61  ;  /* The databa
3a60: 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 20 68 6f  se connection ho
3a70: 6c 64 69 6e 67 20 74 68 69 73 20 62 74 72 65 65  lding this btree
3a80: 20 2a 2f 0a 20 20 42 74 53 68 61 72 65 64 20 2a   */.  BtShared *
3a90: 70 42 74 3b 20 20 20 20 20 2f 2a 20 53 68 61 72  pBt;     /* Shar
3aa0: 61 62 6c 65 20 63 6f 6e 74 65 6e 74 20 6f 66 20  able content of 
3ab0: 74 68 69 73 20 62 74 72 65 65 20 2a 2f 0a 20 20  this btree */.  
3ac0: 75 38 20 69 6e 54 72 61 6e 73 3b 20 20 20 20 20  u8 inTrans;     
3ad0: 20 20 20 2f 2a 20 54 52 41 4e 53 5f 4e 4f 4e 45     /* TRANS_NONE
3ae0: 2c 20 54 52 41 4e 53 5f 52 45 41 44 20 6f 72 20  , TRANS_READ or 
3af0: 54 52 41 4e 53 5f 57 52 49 54 45 20 2a 2f 0a 20  TRANS_WRITE */. 
3b00: 20 75 38 20 73 68 61 72 61 62 6c 65 3b 20 20 20   u8 sharable;   
3b10: 20 20 20 20 2f 2a 20 54 72 75 65 20 69 66 20 77      /* True if w
3b20: 65 20 63 61 6e 20 73 68 61 72 65 20 70 42 74 20  e can share pBt 
3b30: 77 69 74 68 20 6f 74 68 65 72 20 70 53 71 6c 69  with other pSqli
3b40: 74 65 20 2a 2f 0a 20 20 75 38 20 6c 6f 63 6b 65  te */.  u8 locke
3b50: 64 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 54 72  d;         /* Tr
3b60: 75 65 20 69 66 20 70 53 71 6c 69 74 65 20 63 75  ue if pSqlite cu
3b70: 72 72 65 6e 74 6c 79 20 68 61 73 20 70 42 74 20  rrently has pBt 
3b80: 6c 6f 63 6b 65 64 20 2a 2f 0a 20 20 69 6e 74 20  locked */.  int 
3b90: 77 61 6e 74 54 6f 4c 6f 63 6b 3b 20 20 20 20 2f  wantToLock;    /
3ba0: 2a 20 4e 75 6d 62 65 72 20 6f 66 20 6e 65 73 74  * Number of nest
3bb0: 65 64 20 63 61 6c 6c 73 20 74 6f 20 73 71 6c 69  ed calls to sqli
3bc0: 74 65 33 42 74 72 65 65 45 6e 74 65 72 28 29 20  te3BtreeEnter() 
3bd0: 2a 2f 0a 20 20 42 74 72 65 65 20 2a 70 4e 65 78  */.  Btree *pNex
3be0: 74 3b 20 20 20 20 20 20 2f 2a 20 4c 69 73 74 20  t;      /* List 
3bf0: 6f 66 20 6f 74 68 65 72 20 73 68 61 72 61 62 6c  of other sharabl
3c00: 65 20 42 74 72 65 65 73 20 66 72 6f 6d 20 74 68  e Btrees from th
3c10: 65 20 73 61 6d 65 20 70 53 71 6c 69 74 65 20 2a  e same pSqlite *
3c20: 2f 0a 20 20 42 74 72 65 65 20 2a 70 50 72 65 76  /.  Btree *pPrev
3c30: 3b 20 20 20 20 20 20 2f 2a 20 42 61 63 6b 20 70  ;      /* Back p
3c40: 6f 69 6e 74 65 72 20 6f 66 20 74 68 65 20 73 61  ointer of the sa
3c50: 6d 65 20 6c 69 73 74 20 2a 2f 0a 7d 3b 0a 0a 2f  me list */.};../
3c60: 2a 0a 2a 2a 20 42 74 72 65 65 2e 69 6e 54 72 61  *.** Btree.inTra
3c70: 6e 73 20 6d 61 79 20 74 61 6b 65 20 6f 6e 65 20  ns may take one 
3c80: 6f 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67  of the following
3c90: 20 76 61 6c 75 65 73 2e 0a 2a 2a 0a 2a 2a 20 49   values..**.** I
3ca0: 66 20 74 68 65 20 73 68 61 72 65 64 2d 64 61 74  f the shared-dat
3cb0: 61 20 65 78 74 65 6e 73 69 6f 6e 20 69 73 20 65  a extension is e
3cc0: 6e 61 62 6c 65 64 2c 20 74 68 65 72 65 20 6d 61  nabled, there ma
3cd0: 79 20 62 65 20 6d 75 6c 74 69 70 6c 65 20 75 73  y be multiple us
3ce0: 65 72 73 0a 2a 2a 20 6f 66 20 74 68 65 20 42 74  ers.** of the Bt
3cf0: 72 65 65 20 73 74 72 75 63 74 75 72 65 2e 20 41  ree structure. A
3d00: 74 20 6d 6f 73 74 20 6f 6e 65 20 6f 66 20 74 68  t most one of th
3d10: 65 73 65 20 6d 61 79 20 6f 70 65 6e 20 61 20 77  ese may open a w
3d20: 72 69 74 65 20 74 72 61 6e 73 61 63 74 69 6f 6e  rite transaction
3d30: 2c 0a 2a 2a 20 62 75 74 20 61 6e 79 20 6e 75 6d  ,.** but any num
3d40: 62 65 72 20 6d 61 79 20 68 61 76 65 20 61 63 74  ber may have act
3d50: 69 76 65 20 72 65 61 64 20 74 72 61 6e 73 61 63  ive read transac
3d60: 74 69 6f 6e 73 2e 0a 2a 2f 0a 23 64 65 66 69 6e  tions..*/.#defin
3d70: 65 20 54 52 41 4e 53 5f 4e 4f 4e 45 20 20 30 0a  e TRANS_NONE  0.
3d80: 23 64 65 66 69 6e 65 20 54 52 41 4e 53 5f 52 45  #define TRANS_RE
3d90: 41 44 20 20 31 0a 23 64 65 66 69 6e 65 20 54 52  AD  1.#define TR
3da0: 41 4e 53 5f 57 52 49 54 45 20 32 0a 0a 2f 2a 0a  ANS_WRITE 2../*.
3db0: 2a 2a 20 41 6e 20 69 6e 73 74 61 6e 63 65 20 6f  ** An instance o
3dc0: 66 20 74 68 69 73 20 6f 62 6a 65 63 74 20 72 65  f this object re
3dd0: 70 72 65 73 65 6e 74 73 20 61 20 73 69 6e 67 6c  presents a singl
3de0: 65 20 64 61 74 61 62 61 73 65 20 66 69 6c 65 2e  e database file.
3df0: 0a 2a 2a 20 0a 2a 2a 20 41 20 73 69 6e 67 6c 65  .** .** A single
3e00: 20 64 61 74 61 62 61 73 65 20 66 69 6c 65 20 63   database file c
3e10: 61 6e 20 62 65 20 69 6e 20 75 73 65 20 61 73 20  an be in use as 
3e20: 74 68 65 20 73 61 6d 65 20 74 69 6d 65 20 62 79  the same time by
3e30: 20 74 77 6f 0a 2a 2a 20 6f 72 20 6d 6f 72 65 20   two.** or more 
3e40: 64 61 74 61 62 61 73 65 20 63 6f 6e 6e 65 63 74  database connect
3e50: 69 6f 6e 73 2e 20 20 57 68 65 6e 20 74 77 6f 20  ions.  When two 
3e60: 6f 72 20 6d 6f 72 65 20 63 6f 6e 6e 65 63 74 69  or more connecti
3e70: 6f 6e 73 20 61 72 65 0a 2a 2a 20 73 68 61 72 69  ons are.** shari
3e80: 6e 67 20 74 68 65 20 73 61 6d 65 20 64 61 74 61  ng the same data
3e90: 62 61 73 65 20 66 69 6c 65 2c 20 65 61 63 68 20  base file, each 
3ea0: 63 6f 6e 6e 65 63 74 69 6f 6e 20 68 61 73 20 69  connection has i
3eb0: 74 20 6f 77 6e 0a 2a 2a 20 70 72 69 76 61 74 65  t own.** private
3ec0: 20 42 74 72 65 65 20 6f 62 6a 65 63 74 20 66 6f   Btree object fo
3ed0: 72 20 74 68 65 20 66 69 6c 65 20 61 6e 64 20 65  r the file and e
3ee0: 61 63 68 20 6f 66 20 74 68 6f 73 65 20 42 74 72  ach of those Btr
3ef0: 65 65 73 20 70 6f 69 6e 74 73 0a 2a 2a 20 74 6f  ees points.** to
3f00: 20 74 68 69 73 20 6f 6e 65 20 42 74 53 68 61 72   this one BtShar
3f10: 65 64 20 6f 62 6a 65 63 74 2e 20 20 42 74 53 68  ed object.  BtSh
3f20: 61 72 65 64 2e 6e 52 65 66 20 69 73 20 74 68 65  ared.nRef is the
3f30: 20 6e 75 6d 62 65 72 20 6f 66 0a 2a 2a 20 63 6f   number of.** co
3f40: 6e 6e 65 63 74 69 6f 6e 73 20 63 75 72 72 65 6e  nnections curren
3f50: 74 6c 79 20 73 68 61 72 69 6e 67 20 74 68 69 73  tly sharing this
3f60: 20 64 61 74 61 62 61 73 65 20 66 69 6c 65 2e 0a   database file..
3f70: 2a 2a 0a 2a 2a 20 46 69 65 6c 64 73 20 69 6e 20  **.** Fields in 
3f80: 74 68 69 73 20 73 74 72 75 63 74 75 72 65 20 61  this structure a
3f90: 72 65 20 61 63 63 65 73 73 65 64 20 75 6e 64 65  re accessed unde
3fa0: 72 20 74 68 65 20 42 74 53 68 61 72 65 64 2e 6d  r the BtShared.m
3fb0: 75 74 65 78 0a 2a 2a 20 6d 75 74 65 78 2c 20 65  utex.** mutex, e
3fc0: 78 63 65 70 74 20 66 6f 72 20 6e 52 65 66 20 61  xcept for nRef a
3fd0: 6e 64 20 70 4e 65 78 74 20 77 68 69 63 68 20 61  nd pNext which a
3fe0: 72 65 20 61 63 63 65 73 73 65 64 20 75 6e 64 65  re accessed unde
3ff0: 72 20 74 68 65 0a 2a 2a 20 67 6c 6f 62 61 6c 20  r the.** global 
4000: 53 51 4c 49 54 45 5f 4d 55 54 45 58 5f 53 54 41  SQLITE_MUTEX_STA
4010: 54 49 43 5f 4d 41 53 54 45 52 20 6d 75 74 65 78  TIC_MASTER mutex
4020: 2e 20 20 54 68 65 20 70 50 61 67 65 72 20 66 69  .  The pPager fi
4030: 65 6c 64 0a 2a 2a 20 6d 61 79 20 6e 6f 74 20 62  eld.** may not b
4040: 65 20 6d 6f 64 69 66 69 65 64 20 6f 6e 63 65 20  e modified once 
4050: 69 74 20 69 73 20 69 6e 69 74 69 61 6c 6c 79 20  it is initially 
4060: 73 65 74 20 61 73 20 6c 6f 6e 67 20 61 73 20 6e  set as long as n
4070: 52 65 66 3e 30 2e 0a 2a 2a 20 54 68 65 20 70 53  Ref>0..** The pS
4080: 63 68 65 6d 61 20 66 69 65 6c 64 20 6d 61 79 20  chema field may 
4090: 62 65 20 73 65 74 20 6f 6e 63 65 20 75 6e 64 65  be set once unde
40a0: 72 20 42 74 53 68 61 72 65 64 2e 6d 75 74 65 78  r BtShared.mutex
40b0: 20 61 6e 64 0a 2a 2a 20 74 68 65 72 65 61 66 74   and.** thereaft
40c0: 65 72 20 69 73 20 75 6e 63 68 61 6e 67 65 64 20  er is unchanged 
40d0: 61 73 20 6c 6f 6e 67 20 61 73 20 6e 52 65 66 3e  as long as nRef>
40e0: 30 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 42 74 53  0..*/.struct BtS
40f0: 68 61 72 65 64 20 7b 0a 20 20 50 61 67 65 72 20  hared {.  Pager 
4100: 2a 70 50 61 67 65 72 3b 20 20 20 20 20 20 20 20  *pPager;        
4110: 2f 2a 20 54 68 65 20 70 61 67 65 20 63 61 63 68  /* The page cach
4120: 65 20 2a 2f 0a 20 20 42 74 43 75 72 73 6f 72 20  e */.  BtCursor 
4130: 2a 70 43 75 72 73 6f 72 3b 20 20 20 20 2f 2a 20  *pCursor;    /* 
4140: 41 20 6c 69 73 74 20 6f 66 20 61 6c 6c 20 6f 70  A list of all op
4150: 65 6e 20 63 75 72 73 6f 72 73 20 2a 2f 0a 20 20  en cursors */.  
4160: 4d 65 6d 50 61 67 65 20 2a 70 50 61 67 65 31 3b  MemPage *pPage1;
4170: 20 20 20 20 20 20 2f 2a 20 46 69 72 73 74 20 70        /* First p
4180: 61 67 65 20 6f 66 20 74 68 65 20 64 61 74 61 62  age of the datab
4190: 61 73 65 20 2a 2f 0a 20 20 75 38 20 69 6e 53 74  ase */.  u8 inSt
41a0: 6d 74 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f  mt;            /
41b0: 2a 20 54 72 75 65 20 69 66 20 77 65 20 61 72 65  * True if we are
41c0: 20 69 6e 20 61 20 73 74 61 74 65 6d 65 6e 74 20   in a statement 
41d0: 73 75 62 74 72 61 6e 73 61 63 74 69 6f 6e 20 2a  subtransaction *
41e0: 2f 0a 20 20 75 38 20 72 65 61 64 4f 6e 6c 79 3b  /.  u8 readOnly;
41f0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75            /* Tru
4200: 65 20 69 66 20 74 68 65 20 75 6e 64 65 72 6c 79  e if the underly
4210: 69 6e 67 20 66 69 6c 65 20 69 73 20 72 65 61 64  ing file is read
4220: 6f 6e 6c 79 20 2a 2f 0a 20 20 75 38 20 6d 61 78  only */.  u8 max
4230: 45 6d 62 65 64 46 72 61 63 3b 20 20 20 20 20 20  EmbedFrac;      
4240: 2f 2a 20 4d 61 78 69 6d 75 6d 20 70 61 79 6c 6f  /* Maximum paylo
4250: 61 64 20 61 73 20 25 20 6f 66 20 74 6f 74 61 6c  ad as % of total
4260: 20 70 61 67 65 20 73 69 7a 65 20 2a 2f 0a 20 20   page size */.  
4270: 75 38 20 6d 69 6e 45 6d 62 65 64 46 72 61 63 3b  u8 minEmbedFrac;
4280: 20 20 20 20 20 20 2f 2a 20 4d 69 6e 69 6d 75 6d        /* Minimum
4290: 20 70 61 79 6c 6f 61 64 20 61 73 20 25 20 6f 66   payload as % of
42a0: 20 74 6f 74 61 6c 20 70 61 67 65 20 73 69 7a 65   total page size
42b0: 20 2a 2f 0a 20 20 75 38 20 6d 69 6e 4c 65 61 66   */.  u8 minLeaf
42c0: 46 72 61 63 3b 20 20 20 20 20 20 20 2f 2a 20 4d  Frac;       /* M
42d0: 69 6e 69 6d 75 6d 20 6c 65 61 66 20 70 61 79 6c  inimum leaf payl
42e0: 6f 61 64 20 61 73 20 25 20 6f 66 20 74 6f 74 61  oad as % of tota
42f0: 6c 20 70 61 67 65 20 73 69 7a 65 20 2a 2f 0a 20  l page size */. 
4300: 20 75 38 20 70 61 67 65 53 69 7a 65 46 69 78 65   u8 pageSizeFixe
4310: 64 3b 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69  d;     /* True i
4320: 66 20 74 68 65 20 70 61 67 65 20 73 69 7a 65 20  f the page size 
4330: 63 61 6e 20 6e 6f 20 6c 6f 6e 67 65 72 20 62 65  can no longer be
4340: 20 63 68 61 6e 67 65 64 20 2a 2f 0a 23 69 66 6e   changed */.#ifn
4350: 64 65 66 20 53 51 4c 49 54 45 5f 4f 4d 49 54 5f  def SQLITE_OMIT_
4360: 41 55 54 4f 56 41 43 55 55 4d 0a 20 20 75 38 20  AUTOVACUUM.  u8 
4370: 61 75 74 6f 56 61 63 75 75 6d 3b 20 20 20 20 20  autoVacuum;     
4380: 20 20 20 2f 2a 20 54 72 75 65 20 69 66 20 61 75     /* True if au
4390: 74 6f 2d 76 61 63 75 75 6d 20 69 73 20 65 6e 61  to-vacuum is ena
43a0: 62 6c 65 64 20 2a 2f 0a 20 20 75 38 20 69 6e 63  bled */.  u8 inc
43b0: 72 56 61 63 75 75 6d 3b 20 20 20 20 20 20 20 20  rVacuum;        
43c0: 2f 2a 20 54 72 75 65 20 69 66 20 69 6e 63 72 2d  /* True if incr-
43d0: 76 61 63 75 75 6d 20 69 73 20 65 6e 61 62 6c 65  vacuum is enable
43e0: 64 20 2a 2f 0a 20 20 50 67 6e 6f 20 6e 54 72 75  d */.  Pgno nTru
43f0: 6e 63 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20  nc;          /* 
4400: 4e 6f 6e 2d 7a 65 72 6f 20 69 66 20 74 68 65 20  Non-zero if the 
4410: 64 62 20 77 69 6c 6c 20 62 65 20 74 72 75 6e 63  db will be trunc
4420: 61 74 65 64 20 28 69 6e 63 72 20 76 61 63 75 75  ated (incr vacuu
4430: 6d 29 20 2a 2f 0a 23 65 6e 64 69 66 0a 20 20 75  m) */.#endif.  u
4440: 31 36 20 70 61 67 65 53 69 7a 65 3b 20 20 20 20  16 pageSize;    
4450: 20 20 20 20 20 2f 2a 20 54 6f 74 61 6c 20 6e 75       /* Total nu
4460: 6d 62 65 72 20 6f 66 20 62 79 74 65 73 20 6f 6e  mber of bytes on
4470: 20 61 20 70 61 67 65 20 2a 2f 0a 20 20 75 31 36   a page */.  u16
4480: 20 75 73 61 62 6c 65 53 69 7a 65 3b 20 20 20 20   usableSize;    
4490: 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20     /* Number of 
44a0: 75 73 61 62 6c 65 20 62 79 74 65 73 20 6f 6e 20  usable bytes on 
44b0: 65 61 63 68 20 70 61 67 65 20 2a 2f 0a 20 20 69  each page */.  i
44c0: 6e 74 20 6d 61 78 4c 6f 63 61 6c 3b 20 20 20 20  nt maxLocal;    
44d0: 20 20 20 20 20 2f 2a 20 4d 61 78 69 6d 75 6d 20       /* Maximum 
44e0: 6c 6f 63 61 6c 20 70 61 79 6c 6f 61 64 20 69 6e  local payload in
44f0: 20 6e 6f 6e 2d 4c 45 41 46 44 41 54 41 20 74 61   non-LEAFDATA ta
4500: 62 6c 65 73 20 2a 2f 0a 20 20 69 6e 74 20 6d 69  bles */.  int mi
4510: 6e 4c 6f 63 61 6c 3b 20 20 20 20 20 20 20 20 20  nLocal;         
4520: 2f 2a 20 4d 69 6e 69 6d 75 6d 20 6c 6f 63 61 6c  /* Minimum local
4530: 20 70 61 79 6c 6f 61 64 20 69 6e 20 6e 6f 6e 2d   payload in non-
4540: 4c 45 41 46 44 41 54 41 20 74 61 62 6c 65 73 20  LEAFDATA tables 
4550: 2a 2f 0a 20 20 69 6e 74 20 6d 61 78 4c 65 61 66  */.  int maxLeaf
4560: 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4d 61  ;          /* Ma
4570: 78 69 6d 75 6d 20 6c 6f 63 61 6c 20 70 61 79 6c  ximum local payl
4580: 6f 61 64 20 69 6e 20 61 20 4c 45 41 46 44 41 54  oad in a LEAFDAT
4590: 41 20 74 61 62 6c 65 20 2a 2f 0a 20 20 69 6e 74  A table */.  int
45a0: 20 6d 69 6e 4c 65 61 66 3b 20 20 20 20 20 20 20   minLeaf;       
45b0: 20 20 20 2f 2a 20 4d 69 6e 69 6d 75 6d 20 6c 6f     /* Minimum lo
45c0: 63 61 6c 20 70 61 79 6c 6f 61 64 20 69 6e 20 61  cal payload in a
45d0: 20 4c 45 41 46 44 41 54 41 20 74 61 62 6c 65 20   LEAFDATA table 
45e0: 2a 2f 0a 20 20 42 75 73 79 48 61 6e 64 6c 65 72  */.  BusyHandler
45f0: 20 2a 70 42 75 73 79 48 61 6e 64 6c 65 72 3b 20   *pBusyHandler; 
4600: 20 20 2f 2a 20 43 61 6c 6c 62 61 63 6b 20 66 6f    /* Callback fo
4610: 72 20 77 68 65 6e 20 74 68 65 72 65 20 69 73 20  r when there is 
4620: 6c 6f 63 6b 20 63 6f 6e 74 65 6e 74 69 6f 6e 20  lock contention 
4630: 2a 2f 0a 20 20 75 38 20 69 6e 54 72 61 6e 73 61  */.  u8 inTransa
4640: 63 74 69 6f 6e 3b 20 20 20 20 20 2f 2a 20 54 72  ction;     /* Tr
4650: 61 6e 73 61 63 74 69 6f 6e 20 73 74 61 74 65 20  ansaction state 
4660: 2a 2f 0a 20 20 69 6e 74 20 6e 54 72 61 6e 73 61  */.  int nTransa
4670: 63 74 69 6f 6e 3b 20 20 20 20 20 2f 2a 20 4e 75  ction;     /* Nu
4680: 6d 62 65 72 20 6f 66 20 6f 70 65 6e 20 74 72 61  mber of open tra
4690: 6e 73 61 63 74 69 6f 6e 73 20 28 72 65 61 64 20  nsactions (read 
46a0: 2b 20 77 72 69 74 65 29 20 2a 2f 0a 20 20 76 6f  + write) */.  vo
46b0: 69 64 20 2a 70 53 63 68 65 6d 61 3b 20 20 20 20  id *pSchema;    
46c0: 20 20 20 20 2f 2a 20 50 6f 69 6e 74 65 72 20 74      /* Pointer t
46d0: 6f 20 73 70 61 63 65 20 61 6c 6c 6f 63 61 74 65  o space allocate
46e0: 64 20 62 79 20 73 71 6c 69 74 65 33 42 74 72 65  d by sqlite3Btre
46f0: 65 53 63 68 65 6d 61 28 29 20 2a 2f 0a 20 20 76  eSchema() */.  v
4700: 6f 69 64 20 28 2a 78 46 72 65 65 53 63 68 65 6d  oid (*xFreeSchem
4710: 61 29 28 76 6f 69 64 2a 29 3b 20 20 2f 2a 20 44  a)(void*);  /* D
4720: 65 73 74 72 75 63 74 6f 72 20 66 6f 72 20 42 74  estructor for Bt
4730: 53 68 61 72 65 64 2e 70 53 63 68 65 6d 61 20 2a  Shared.pSchema *
4740: 2f 0a 20 20 73 71 6c 69 74 65 33 5f 6d 75 74 65  /.  sqlite3_mute
4750: 78 20 2a 6d 75 74 65 78 3b 20 2f 2a 20 4e 6f 6e  x *mutex; /* Non
4760: 2d 72 65 63 75 72 73 69 76 65 20 6d 75 74 65 78  -recursive mutex
4770: 20 72 65 71 75 69 72 65 64 20 74 6f 20 61 63 63   required to acc
4780: 65 73 73 20 74 68 69 73 20 73 74 72 75 63 74 20  ess this struct 
4790: 2a 2f 0a 23 69 66 6e 64 65 66 20 53 51 4c 49 54  */.#ifndef SQLIT
47a0: 45 5f 4f 4d 49 54 5f 53 48 41 52 45 44 5f 43 41  E_OMIT_SHARED_CA
47b0: 43 48 45 0a 20 20 69 6e 74 20 6e 52 65 66 3b 20  CHE.  int nRef; 
47c0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e              /* N
47d0: 75 6d 62 65 72 20 6f 66 20 72 65 66 65 72 65 6e  umber of referen
47e0: 63 65 73 20 74 6f 20 74 68 69 73 20 73 74 72 75  ces to this stru
47f0: 63 74 75 72 65 20 2a 2f 0a 20 20 42 74 53 68 61  cture */.  BtSha
4800: 72 65 64 20 2a 70 4e 65 78 74 3b 20 20 20 20 20  red *pNext;     
4810: 20 2f 2a 20 4e 65 78 74 20 6f 6e 20 61 20 6c 69   /* Next on a li
4820: 73 74 20 6f 66 20 73 68 61 72 61 62 6c 65 20 42  st of sharable B
4830: 74 53 68 61 72 65 64 20 73 74 72 75 63 74 73 20  tShared structs 
4840: 2a 2f 0a 20 20 42 74 4c 6f 63 6b 20 2a 70 4c 6f  */.  BtLock *pLo
4850: 63 6b 3b 20 20 20 20 20 20 20 20 2f 2a 20 4c 69  ck;        /* Li
4860: 73 74 20 6f 66 20 6c 6f 63 6b 73 20 68 65 6c 64  st of locks held
4870: 20 6f 6e 20 74 68 69 73 20 73 68 61 72 65 64 2d   on this shared-
4880: 62 74 72 65 65 20 73 74 72 75 63 74 20 2a 2f 0a  btree struct */.
4890: 23 65 6e 64 69 66 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a  #endif.};../*.**
48a0: 20 41 6e 20 69 6e 73 74 61 6e 63 65 20 6f 66 20   An instance of 
48b0: 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 73 74  the following st
48c0: 72 75 63 74 75 72 65 20 69 73 20 75 73 65 64 20  ructure is used 
48d0: 74 6f 20 68 6f 6c 64 20 69 6e 66 6f 72 6d 61 74  to hold informat
48e0: 69 6f 6e 0a 2a 2a 20 61 62 6f 75 74 20 61 20 63  ion.** about a c
48f0: 65 6c 6c 2e 20 20 54 68 65 20 70 61 72 73 65 43  ell.  The parseC
4900: 65 6c 6c 50 74 72 28 29 20 66 75 6e 63 74 69 6f  ellPtr() functio
4910: 6e 20 66 69 6c 6c 73 20 69 6e 20 74 68 69 73 20  n fills in this 
4920: 73 74 72 75 63 74 75 72 65 0a 2a 2a 20 62 61 73  structure.** bas
4930: 65 64 20 6f 6e 20 69 6e 66 6f 72 6d 61 74 69 6f  ed on informatio
4940: 6e 20 65 78 74 72 61 63 74 20 66 72 6f 6d 20 74  n extract from t
4950: 68 65 20 72 61 77 20 64 69 73 6b 20 70 61 67 65  he raw disk page
4960: 2e 0a 2a 2f 0a 74 79 70 65 64 65 66 20 73 74 72  ..*/.typedef str
4970: 75 63 74 20 43 65 6c 6c 49 6e 66 6f 20 43 65 6c  uct CellInfo Cel
4980: 6c 49 6e 66 6f 3b 0a 73 74 72 75 63 74 20 43 65  lInfo;.struct Ce
4990: 6c 6c 49 6e 66 6f 20 7b 0a 20 20 75 38 20 2a 70  llInfo {.  u8 *p
49a0: 43 65 6c 6c 3b 20 20 20 20 20 2f 2a 20 50 6f 69  Cell;     /* Poi
49b0: 6e 74 65 72 20 74 6f 20 74 68 65 20 73 74 61 72  nter to the star
49c0: 74 20 6f 66 20 63 65 6c 6c 20 63 6f 6e 74 65 6e  t of cell conten
49d0: 74 20 2a 2f 0a 20 20 69 36 34 20 6e 4b 65 79 3b  t */.  i64 nKey;
49e0: 20 20 20 20 20 20 2f 2a 20 54 68 65 20 6b 65 79        /* The key
49f0: 20 66 6f 72 20 49 4e 54 4b 45 59 20 74 61 62 6c   for INTKEY tabl
4a00: 65 73 2c 20 6f 72 20 6e 75 6d 62 65 72 20 6f 66  es, or number of
4a10: 20 62 79 74 65 73 20 69 6e 20 6b 65 79 20 2a 2f   bytes in key */
4a20: 0a 20 20 75 33 32 20 6e 44 61 74 61 3b 20 20 20  .  u32 nData;   
4a30: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 62    /* Number of b
4a40: 79 74 65 73 20 6f 66 20 64 61 74 61 20 2a 2f 0a  ytes of data */.
4a50: 20 20 75 33 32 20 6e 50 61 79 6c 6f 61 64 3b 20    u32 nPayload; 
4a60: 20 2f 2a 20 54 6f 74 61 6c 20 61 6d 6f 75 6e 74   /* Total amount
4a70: 20 6f 66 20 70 61 79 6c 6f 61 64 20 2a 2f 0a 20   of payload */. 
4a80: 20 75 31 36 20 6e 48 65 61 64 65 72 3b 20 20 20   u16 nHeader;   
4a90: 2f 2a 20 53 69 7a 65 20 6f 66 20 74 68 65 20 63  /* Size of the c
4aa0: 65 6c 6c 20 63 6f 6e 74 65 6e 74 20 68 65 61 64  ell content head
4ab0: 65 72 20 69 6e 20 62 79 74 65 73 20 2a 2f 0a 20  er in bytes */. 
4ac0: 20 75 31 36 20 6e 4c 6f 63 61 6c 3b 20 20 20 20   u16 nLocal;    
4ad0: 2f 2a 20 41 6d 6f 75 6e 74 20 6f 66 20 70 61 79  /* Amount of pay
4ae0: 6c 6f 61 64 20 68 65 6c 64 20 6c 6f 63 61 6c 6c  load held locall
4af0: 79 20 2a 2f 0a 20 20 75 31 36 20 69 4f 76 65 72  y */.  u16 iOver
4b00: 66 6c 6f 77 3b 20 2f 2a 20 4f 66 66 73 65 74 20  flow; /* Offset 
4b10: 74 6f 20 6f 76 65 72 66 6c 6f 77 20 70 61 67 65  to overflow page
4b20: 20 6e 75 6d 62 65 72 2e 20 20 5a 65 72 6f 20 69   number.  Zero i
4b30: 66 20 6e 6f 20 6f 76 65 72 66 6c 6f 77 20 2a 2f  f no overflow */
4b40: 0a 20 20 75 31 36 20 6e 53 69 7a 65 3b 20 20 20  .  u16 nSize;   
4b50: 20 20 2f 2a 20 53 69 7a 65 20 6f 66 20 74 68 65    /* Size of the
4b60: 20 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 20 6f 6e   cell content on
4b70: 20 74 68 65 20 6d 61 69 6e 20 62 2d 74 72 65 65   the main b-tree
4b80: 20 70 61 67 65 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a   page */.};../*.
4b90: 2a 2a 20 41 20 63 75 72 73 6f 72 20 69 73 20 61  ** A cursor is a
4ba0: 20 70 6f 69 6e 74 65 72 20 74 6f 20 61 20 70 61   pointer to a pa
4bb0: 72 74 69 63 75 6c 61 72 20 65 6e 74 72 79 20 77  rticular entry w
4bc0: 69 74 68 69 6e 20 61 20 70 61 72 74 69 63 75 6c  ithin a particul
4bd0: 61 72 0a 2a 2a 20 62 2d 74 72 65 65 20 77 69 74  ar.** b-tree wit
4be0: 68 69 6e 20 61 20 64 61 74 61 62 61 73 65 20 66  hin a database f
4bf0: 69 6c 65 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 65  ile..**.** The e
4c00: 6e 74 72 79 20 69 73 20 69 64 65 6e 74 69 66 69  ntry is identifi
4c10: 65 64 20 62 79 20 69 74 73 20 4d 65 6d 50 61 67  ed by its MemPag
4c20: 65 20 61 6e 64 20 74 68 65 20 69 6e 64 65 78 20  e and the index 
4c30: 69 6e 0a 2a 2a 20 4d 65 6d 50 61 67 65 2e 61 43  in.** MemPage.aC
4c40: 65 6c 6c 5b 5d 20 6f 66 20 74 68 65 20 65 6e 74  ell[] of the ent
4c50: 72 79 2e 0a 2a 2a 0a 2a 2a 20 57 68 65 6e 20 61  ry..**.** When a
4c60: 20 73 69 6e 67 6c 65 20 64 61 74 61 62 61 73 65   single database
4c70: 20 66 69 6c 65 20 63 61 6e 20 73 68 61 72 65 64   file can shared
4c80: 20 62 79 20 74 77 6f 20 6d 6f 72 65 20 64 61 74   by two more dat
4c90: 61 62 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e  abase connection
4ca0: 73 2c 0a 2a 2a 20 62 75 74 20 63 75 72 73 6f 72  s,.** but cursor
4cb0: 73 20 63 61 6e 6e 6f 74 20 62 65 20 73 68 61 72  s cannot be shar
4cc0: 65 64 2e 20 20 45 61 63 68 20 63 75 72 73 6f 72  ed.  Each cursor
4cd0: 20 69 73 20 61 73 73 6f 63 69 61 74 65 64 20 77   is associated w
4ce0: 69 74 68 20 61 0a 2a 2a 20 70 61 72 74 69 63 75  ith a.** particu
4cf0: 6c 61 72 20 64 61 74 61 62 61 73 65 20 63 6f 6e  lar database con
4d00: 6e 65 63 74 69 6f 6e 20 69 64 65 6e 74 69 66 69  nection identifi
4d10: 65 64 20 42 74 43 75 72 73 6f 72 2e 70 42 74 72  ed BtCursor.pBtr
4d20: 65 65 2e 70 53 71 6c 69 74 65 2e 0a 2a 2a 0a 2a  ee.pSqlite..**.*
4d30: 2a 20 46 69 65 6c 64 73 20 69 6e 20 74 68 69 73  * Fields in this
4d40: 20 73 74 72 75 63 74 75 72 65 20 61 72 65 20 61   structure are a
4d50: 63 63 65 73 73 65 64 20 75 6e 64 65 72 20 74 68  ccessed under th
4d60: 65 20 42 74 53 68 61 72 65 64 2e 6d 75 74 65 78  e BtShared.mutex
4d70: 0a 2a 2a 20 66 6f 75 6e 64 20 61 74 20 73 65 6c  .** found at sel
4d80: 66 2d 3e 70 42 74 2d 3e 6d 75 74 65 78 2e 20 0a  f->pBt->mutex. .
4d90: 2a 2f 0a 73 74 72 75 63 74 20 42 74 43 75 72 73  */.struct BtCurs
4da0: 6f 72 20 7b 0a 20 20 42 74 72 65 65 20 2a 70 42  or {.  Btree *pB
4db0: 74 72 65 65 3b 20 20 20 20 20 20 20 20 20 20 20  tree;           
4dc0: 20 2f 2a 20 54 68 65 20 42 74 72 65 65 20 74 6f   /* The Btree to
4dd0: 20 77 68 69 63 68 20 74 68 69 73 20 63 75 72 73   which this curs
4de0: 6f 72 20 62 65 6c 6f 6e 67 73 20 2a 2f 0a 20 20  or belongs */.  
4df0: 42 74 53 68 61 72 65 64 20 2a 70 42 74 3b 20 20  BtShared *pBt;  
4e00: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65            /* The
4e10: 20 42 74 53 68 61 72 65 64 20 74 68 69 73 20 63   BtShared this c
4e20: 75 72 73 6f 72 20 70 6f 69 6e 74 73 20 74 6f 20  ursor points to 
4e30: 2a 2f 0a 20 20 42 74 43 75 72 73 6f 72 20 2a 70  */.  BtCursor *p
4e40: 4e 65 78 74 2c 20 2a 70 50 72 65 76 3b 20 20 2f  Next, *pPrev;  /
4e50: 2a 20 46 6f 72 6d 73 20 61 20 6c 69 6e 6b 65 64  * Forms a linked
4e60: 20 6c 69 73 74 20 6f 66 20 61 6c 6c 20 63 75 72   list of all cur
4e70: 73 6f 72 73 20 2a 2f 0a 20 20 69 6e 74 20 28 2a  sors */.  int (*
4e80: 78 43 6f 6d 70 61 72 65 29 28 76 6f 69 64 2a 2c  xCompare)(void*,
4e90: 69 6e 74 2c 63 6f 6e 73 74 20 76 6f 69 64 2a 2c  int,const void*,
4ea0: 69 6e 74 2c 63 6f 6e 73 74 20 76 6f 69 64 2a 29  int,const void*)
4eb0: 3b 20 2f 2a 20 4b 65 79 20 63 6f 6d 70 20 66 75  ; /* Key comp fu
4ec0: 6e 63 20 2a 2f 0a 20 20 76 6f 69 64 20 2a 70 41  nc */.  void *pA
4ed0: 72 67 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  rg;             
4ee0: 20 20 2f 2a 20 46 69 72 73 74 20 61 72 67 20 74    /* First arg t
4ef0: 6f 20 78 43 6f 6d 70 61 72 65 28 29 20 2a 2f 0a  o xCompare() */.
4f00: 20 20 50 67 6e 6f 20 70 67 6e 6f 52 6f 6f 74 3b    Pgno pgnoRoot;
4f10: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54              /* T
4f20: 68 65 20 72 6f 6f 74 20 70 61 67 65 20 6f 66 20  he root page of 
4f30: 74 68 69 73 20 74 72 65 65 20 2a 2f 0a 20 20 4d  this tree */.  M
4f40: 65 6d 50 61 67 65 20 2a 70 50 61 67 65 3b 20 20  emPage *pPage;  
4f50: 20 20 20 20 20 20 20 20 20 2f 2a 20 50 61 67 65           /* Page
4f60: 20 74 68 61 74 20 63 6f 6e 74 61 69 6e 73 20 74   that contains t
4f70: 68 65 20 65 6e 74 72 79 20 2a 2f 0a 20 20 69 6e  he entry */.  in
4f80: 74 20 69 64 78 3b 20 20 20 20 20 20 20 20 20 20  t idx;          
4f90: 20 20 20 20 20 20 20 20 2f 2a 20 49 6e 64 65 78          /* Index
4fa0: 20 6f 66 20 74 68 65 20 65 6e 74 72 79 20 69 6e   of the entry in
4fb0: 20 70 50 61 67 65 2d 3e 61 43 65 6c 6c 5b 5d 20   pPage->aCell[] 
4fc0: 2a 2f 0a 20 20 43 65 6c 6c 49 6e 66 6f 20 69 6e  */.  CellInfo in
4fd0: 66 6f 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f  fo;            /
4fe0: 2a 20 41 20 70 61 72 73 65 20 6f 66 20 74 68 65  * A parse of the
4ff0: 20 63 65 6c 6c 20 77 65 20 61 72 65 20 70 6f 69   cell we are poi
5000: 6e 74 69 6e 67 20 61 74 20 2a 2f 0a 20 20 75 38  nting at */.  u8
5010: 20 77 72 46 6c 61 67 3b 20 20 20 20 20 20 20 20   wrFlag;        
5020: 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20          /* True 
5030: 69 66 20 77 72 69 74 61 62 6c 65 20 2a 2f 0a 20  if writable */. 
5040: 20 75 38 20 65 53 74 61 74 65 3b 20 20 20 20 20   u8 eState;     
5050: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4f 6e             /* On
5060: 65 20 6f 66 20 74 68 65 20 43 55 52 53 4f 52 5f  e of the CURSOR_
5070: 58 58 58 20 63 6f 6e 73 74 61 6e 74 73 20 28 73  XXX constants (s
5080: 65 65 20 62 65 6c 6f 77 29 20 2a 2f 0a 20 20 76  ee below) */.  v
5090: 6f 69 64 20 2a 70 4b 65 79 3b 20 20 20 20 20 20  oid *pKey;      
50a0: 2f 2a 20 53 61 76 65 64 20 6b 65 79 20 74 68 61  /* Saved key tha
50b0: 74 20 77 61 73 20 63 75 72 73 6f 72 27 73 20 6c  t was cursor's l
50c0: 61 73 74 20 6b 6e 6f 77 6e 20 70 6f 73 69 74 69  ast known positi
50d0: 6f 6e 20 2a 2f 0a 20 20 69 36 34 20 6e 4b 65 79  on */.  i64 nKey
50e0: 3b 20 20 20 20 20 20 20 20 2f 2a 20 53 69 7a 65  ;        /* Size
50f0: 20 6f 66 20 70 4b 65 79 2c 20 6f 72 20 6c 61 73   of pKey, or las
5100: 74 20 69 6e 74 65 67 65 72 20 6b 65 79 20 2a 2f  t integer key */
5110: 0a 20 20 69 6e 74 20 73 6b 69 70 3b 20 20 20 20  .  int skip;    
5120: 20 20 20 20 2f 2a 20 28 73 6b 69 70 3c 30 29 20      /* (skip<0) 
5130: 2d 3e 20 50 72 65 76 28 29 20 69 73 20 61 20 6e  -> Prev() is a n
5140: 6f 2d 6f 70 2e 20 28 73 6b 69 70 3e 30 29 20 2d  o-op. (skip>0) -
5150: 3e 20 4e 65 78 74 28 29 20 69 73 20 2a 2f 0a 23  > Next() is */.#
5160: 69 66 6e 64 65 66 20 53 51 4c 49 54 45 5f 4f 4d  ifndef SQLITE_OM
5170: 49 54 5f 49 4e 43 52 42 4c 4f 42 0a 20 20 75 38  IT_INCRBLOB.  u8
5180: 20 69 73 49 6e 63 72 62 6c 6f 62 48 61 6e 64 6c   isIncrblobHandl
5190: 65 3b 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20  e;      /* True 
51a0: 69 66 20 74 68 69 73 20 63 75 72 73 6f 72 20 69  if this cursor i
51b0: 73 20 61 6e 20 69 6e 63 72 2e 20 69 6f 20 68 61  s an incr. io ha
51c0: 6e 64 6c 65 20 2a 2f 0a 20 20 50 67 6e 6f 20 2a  ndle */.  Pgno *
51d0: 61 4f 76 65 72 66 6c 6f 77 3b 20 20 20 20 20 20  aOverflow;      
51e0: 20 20 20 20 2f 2a 20 43 61 63 68 65 20 6f 66 20      /* Cache of 
51f0: 6f 76 65 72 66 6c 6f 77 20 70 61 67 65 20 6c 6f  overflow page lo
5200: 63 61 74 69 6f 6e 73 20 2a 2f 0a 23 65 6e 64 69  cations */.#endi
5210: 66 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 50 6f 74 65  f.};../*.** Pote
5220: 6e 74 69 61 6c 20 76 61 6c 75 65 73 20 66 6f 72  ntial values for
5230: 20 42 74 43 75 72 73 6f 72 2e 65 53 74 61 74 65   BtCursor.eState
5240: 2e 0a 2a 2a 0a 2a 2a 20 43 55 52 53 4f 52 5f 56  ..**.** CURSOR_V
5250: 41 4c 49 44 3a 0a 2a 2a 20 20 20 43 75 72 73 6f  ALID:.**   Curso
5260: 72 20 70 6f 69 6e 74 73 20 74 6f 20 61 20 76 61  r points to a va
5270: 6c 69 64 20 65 6e 74 72 79 2e 20 67 65 74 50 61  lid entry. getPa
5280: 79 6c 6f 61 64 28 29 20 65 74 63 2e 20 6d 61 79  yload() etc. may
5290: 20 62 65 20 63 61 6c 6c 65 64 2e 0a 2a 2a 0a 2a   be called..**.*
52a0: 2a 20 43 55 52 53 4f 52 5f 49 4e 56 41 4c 49 44  * CURSOR_INVALID
52b0: 3a 0a 2a 2a 20 20 20 43 75 72 73 6f 72 20 64 6f  :.**   Cursor do
52c0: 65 73 20 6e 6f 74 20 70 6f 69 6e 74 20 74 6f 20  es not point to 
52d0: 61 20 76 61 6c 69 64 20 65 6e 74 72 79 2e 20 54  a valid entry. T
52e0: 68 69 73 20 63 61 6e 20 68 61 70 70 65 6e 20 28  his can happen (
52f0: 66 6f 72 20 65 78 61 6d 70 6c 65 29 20 0a 2a 2a  for example) .**
5300: 20 20 20 62 65 63 61 75 73 65 20 74 68 65 20 74     because the t
5310: 61 62 6c 65 20 69 73 20 65 6d 70 74 79 20 6f 72  able is empty or
5320: 20 62 65 63 61 75 73 65 20 42 74 72 65 65 43 75   because BtreeCu
5330: 72 73 6f 72 46 69 72 73 74 28 29 20 68 61 73 20  rsorFirst() has 
5340: 6e 6f 74 20 62 65 65 6e 0a 2a 2a 20 20 20 63 61  not been.**   ca
5350: 6c 6c 65 64 2e 0a 2a 2a 0a 2a 2a 20 43 55 52 53  lled..**.** CURS
5360: 4f 52 5f 52 45 51 55 49 52 45 53 45 45 4b 3a 0a  OR_REQUIRESEEK:.
5370: 2a 2a 20 20 20 54 68 65 20 74 61 62 6c 65 20 74  **   The table t
5380: 68 61 74 20 74 68 69 73 20 63 75 72 73 6f 72 20  hat this cursor 
5390: 77 61 73 20 6f 70 65 6e 65 64 20 6f 6e 20 73 74  was opened on st
53a0: 69 6c 6c 20 65 78 69 73 74 73 2c 20 62 75 74 20  ill exists, but 
53b0: 68 61 73 20 62 65 65 6e 20 0a 2a 2a 20 20 20 6d  has been .**   m
53c0: 6f 64 69 66 69 65 64 20 73 69 6e 63 65 20 74 68  odified since th
53d0: 65 20 63 75 72 73 6f 72 20 77 61 73 20 6c 61 73  e cursor was las
53e0: 74 20 75 73 65 64 2e 20 54 68 65 20 63 75 72 73  t used. The curs
53f0: 6f 72 20 70 6f 73 69 74 69 6f 6e 20 69 73 20 73  or position is s
5400: 61 76 65 64 0a 2a 2a 20 20 20 69 6e 20 76 61 72  aved.**   in var
5410: 69 61 62 6c 65 73 20 42 74 43 75 72 73 6f 72 2e  iables BtCursor.
5420: 70 4b 65 79 20 61 6e 64 20 42 74 43 75 72 73 6f  pKey and BtCurso
5430: 72 2e 6e 4b 65 79 2e 20 57 68 65 6e 20 61 20 63  r.nKey. When a c
5440: 75 72 73 6f 72 20 69 73 20 69 6e 20 0a 2a 2a 20  ursor is in .** 
5450: 20 20 74 68 69 73 20 73 74 61 74 65 2c 20 72 65    this state, re
5460: 73 74 6f 72 65 4f 72 43 6c 65 61 72 43 75 72 73  storeOrClearCurs
5470: 6f 72 50 6f 73 69 74 69 6f 6e 28 29 20 63 61 6e  orPosition() can
5480: 20 62 65 20 63 61 6c 6c 65 64 20 74 6f 20 61 74   be called to at
5490: 74 65 6d 70 74 20 74 6f 0a 2a 2a 20 20 20 73 65  tempt to.**   se
54a0: 65 6b 20 74 68 65 20 63 75 72 73 6f 72 20 74 6f  ek the cursor to
54b0: 20 74 68 65 20 73 61 76 65 64 20 70 6f 73 69 74   the saved posit
54c0: 69 6f 6e 2e 0a 2a 2a 0a 2a 2a 20 43 55 52 53 4f  ion..**.** CURSO
54d0: 52 5f 46 41 55 4c 54 3a 0a 2a 2a 20 20 20 41 20  R_FAULT:.**   A 
54e0: 75 6e 72 65 63 6f 76 65 72 61 62 6c 65 20 65 72  unrecoverable er
54f0: 72 6f 72 20 28 61 6e 20 49 2f 4f 20 65 72 72 6f  ror (an I/O erro
5500: 72 20 6f 72 20 61 20 6d 61 6c 6c 6f 63 20 66 61  r or a malloc fa
5510: 69 6c 75 72 65 29 20 68 61 73 20 6f 63 63 75 72  ilure) has occur
5520: 72 65 64 0a 2a 2a 20 20 20 6f 6e 20 61 20 64 69  red.**   on a di
5530: 66 66 65 72 65 6e 74 20 63 6f 6e 6e 65 63 74 69  fferent connecti
5540: 6f 6e 20 74 68 61 74 20 73 68 61 72 65 73 20 74  on that shares t
5550: 68 65 20 42 74 53 68 61 72 65 64 20 63 61 63 68  he BtShared cach
5560: 65 20 77 69 74 68 20 74 68 69 73 0a 2a 2a 20 20  e with this.**  
5570: 20 63 75 72 73 6f 72 2e 20 20 54 68 65 20 65 72   cursor.  The er
5580: 72 6f 72 20 68 61 73 20 6c 65 66 74 20 74 68 65  ror has left the
5590: 20 63 61 63 68 65 20 69 6e 20 61 6e 20 69 6e 63   cache in an inc
55a0: 6f 6e 73 69 73 74 65 6e 74 20 73 74 61 74 65 2e  onsistent state.
55b0: 0a 2a 2a 20 20 20 44 6f 20 6e 6f 74 68 69 6e 67  .**   Do nothing
55c0: 20 65 6c 73 65 20 77 69 74 68 20 74 68 69 73 20   else with this 
55d0: 63 75 72 73 6f 72 2e 20 20 41 6e 79 20 61 74 74  cursor.  Any att
55e0: 65 6d 70 74 20 74 6f 20 75 73 65 20 74 68 65 20  empt to use the 
55f0: 63 75 72 73 6f 72 0a 2a 2a 20 20 20 73 68 6f 75  cursor.**   shou
5600: 6c 64 20 72 65 74 75 72 6e 20 74 68 65 20 65 72  ld return the er
5610: 72 6f 72 20 63 6f 64 65 20 73 74 6f 72 65 64 20  ror code stored 
5620: 69 6e 20 42 74 43 75 72 73 6f 72 2e 73 6b 69 70  in BtCursor.skip
5630: 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 43 55 52 53  .*/.#define CURS
5640: 4f 52 5f 49 4e 56 41 4c 49 44 20 20 20 20 20 20  OR_INVALID      
5650: 20 20 20 20 20 30 0a 23 64 65 66 69 6e 65 20 43       0.#define C
5660: 55 52 53 4f 52 5f 56 41 4c 49 44 20 20 20 20 20  URSOR_VALID     
5670: 20 20 20 20 20 20 20 20 31 0a 23 64 65 66 69 6e          1.#defin
5680: 65 20 43 55 52 53 4f 52 5f 52 45 51 55 49 52 45  e CURSOR_REQUIRE
5690: 53 45 45 4b 20 20 20 20 20 20 20 32 0a 23 64 65  SEEK       2.#de
56a0: 66 69 6e 65 20 43 55 52 53 4f 52 5f 46 41 55 4c  fine CURSOR_FAUL
56b0: 54 20 20 20 20 20 20 20 20 20 20 20 20 20 33 0a  T             3.
56c0: 0a 2f 2a 0a 2a 2a 20 54 68 65 20 54 52 41 43 45  ./*.** The TRACE
56d0: 20 6d 61 63 72 6f 20 77 69 6c 6c 20 70 72 69 6e   macro will prin
56e0: 74 20 68 69 67 68 2d 6c 65 76 65 6c 20 73 74 61  t high-level sta
56f0: 74 75 73 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20  tus information 
5700: 61 62 6f 75 74 20 74 68 65 0a 2a 2a 20 62 74 72  about the.** btr
5710: 65 65 20 6f 70 65 72 61 74 69 6f 6e 20 77 68 65  ee operation whe
5720: 6e 20 74 68 65 20 67 6c 6f 62 61 6c 20 76 61 72  n the global var
5730: 69 61 62 6c 65 20 73 71 6c 69 74 65 33 5f 62 74  iable sqlite3_bt
5740: 72 65 65 5f 74 72 61 63 65 20 69 73 0a 2a 2a 20  ree_trace is.** 
5750: 65 6e 61 62 6c 65 64 2e 0a 2a 2f 0a 23 69 66 20  enabled..*/.#if 
5760: 53 51 4c 49 54 45 5f 54 45 53 54 0a 23 20 64 65  SQLITE_TEST.# de
5770: 66 69 6e 65 20 54 52 41 43 45 28 58 29 20 20 20  fine TRACE(X)   
5780: 69 66 28 20 73 71 6c 69 74 65 33 5f 62 74 72 65  if( sqlite3_btre
5790: 65 5f 74 72 61 63 65 20 29 7b 20 70 72 69 6e 74  e_trace ){ print
57a0: 66 20 58 3b 20 66 66 6c 75 73 68 28 73 74 64 6f  f X; fflush(stdo
57b0: 75 74 29 3b 20 7d 0a 23 65 6c 73 65 0a 23 20 64  ut); }.#else.# d
57c0: 65 66 69 6e 65 20 54 52 41 43 45 28 58 29 0a 23  efine TRACE(X).#
57d0: 65 6e 64 69 66 0a 0a 2f 2a 0a 2a 2a 20 52 6f 75  endif../*.** Rou
57e0: 74 69 6e 65 73 20 74 6f 20 72 65 61 64 20 61 6e  tines to read an
57f0: 64 20 77 72 69 74 65 20 76 61 72 69 61 62 6c 65  d write variable
5800: 2d 6c 65 6e 67 74 68 20 69 6e 74 65 67 65 72 73  -length integers
5810: 2e 20 20 54 68 65 73 65 20 75 73 65 64 20 74 6f  .  These used to
5820: 0a 2a 2a 20 62 65 20 64 65 66 69 6e 65 64 20 6c  .** be defined l
5830: 6f 63 61 6c 6c 79 2c 20 62 75 74 20 6e 6f 77 20  ocally, but now 
5840: 77 65 20 75 73 65 20 74 68 65 20 76 61 72 69 6e  we use the varin
5850: 74 20 72 6f 75 74 69 6e 65 73 20 69 6e 20 74 68  t routines in th
5860: 65 20 75 74 69 6c 2e 63 0a 2a 2a 20 66 69 6c 65  e util.c.** file
5870: 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 67 65 74  ..*/.#define get
5880: 56 61 72 69 6e 74 20 20 20 20 73 71 6c 69 74 65  Varint    sqlite
5890: 33 47 65 74 56 61 72 69 6e 74 0a 23 64 65 66 69  3GetVarint.#defi
58a0: 6e 65 20 67 65 74 56 61 72 69 6e 74 33 32 28 41  ne getVarint32(A
58b0: 2c 42 29 20 20 28 28 2a 42 3d 2a 28 41 29 29 3c  ,B)  ((*B=*(A))<
58c0: 3d 30 78 37 66 3f 31 3a 73 71 6c 69 74 65 33 47  =0x7f?1:sqlite3G
58d0: 65 74 56 61 72 69 6e 74 33 32 28 41 2c 42 29 29  etVarint32(A,B))
58e0: 0a 23 64 65 66 69 6e 65 20 70 75 74 56 61 72 69  .#define putVari
58f0: 6e 74 20 20 20 20 73 71 6c 69 74 65 33 50 75 74  nt    sqlite3Put
5900: 56 61 72 69 6e 74 0a 0a 2f 2a 20 54 68 65 20 64  Varint../* The d
5910: 61 74 61 62 61 73 65 20 70 61 67 65 20 74 68 65  atabase page the
5920: 20 50 45 4e 44 49 4e 47 5f 42 59 54 45 20 6f 63   PENDING_BYTE oc
5930: 63 75 70 69 65 73 2e 20 54 68 69 73 20 70 61 67  cupies. This pag
5940: 65 20 69 73 20 6e 65 76 65 72 20 75 73 65 64 2e  e is never used.
5950: 0a 2a 2a 20 54 4f 44 4f 3a 20 54 68 69 73 20 6d  .** TODO: This m
5960: 61 63 72 6f 20 69 73 20 76 65 72 79 20 73 69 6d  acro is very sim
5970: 69 6c 61 72 79 20 74 6f 20 50 41 47 45 52 5f 4d  ilary to PAGER_M
5980: 4a 5f 50 47 4e 4f 28 29 20 69 6e 20 70 61 67 65  J_PGNO() in page
5990: 72 2e 63 2e 20 54 68 65 79 0a 2a 2a 20 73 68 6f  r.c. They.** sho
59a0: 75 6c 64 20 70 6f 73 73 69 62 6c 79 20 62 65 20  uld possibly be 
59b0: 63 6f 6e 73 6f 6c 69 64 61 74 65 64 20 28 70 72  consolidated (pr
59c0: 65 73 75 6d 61 62 6c 79 20 69 6e 20 70 61 67 65  esumably in page
59d0: 72 2e 68 29 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 64  r.h)..**.** If d
59e0: 69 73 6b 20 49 2f 4f 20 69 73 20 6f 6d 69 74 74  isk I/O is omitt
59f0: 65 64 20 28 6d 65 61 6e 69 6e 67 20 74 68 61 74  ed (meaning that
5a00: 20 74 68 65 20 64 61 74 61 62 61 73 65 20 69 73   the database is
5a10: 20 73 74 6f 72 65 64 20 70 75 72 65 6c 79 0a 2a   stored purely.*
5a20: 2a 20 69 6e 20 6d 65 6d 6f 72 79 29 20 74 68 65  * in memory) the
5a30: 6e 20 74 68 65 72 65 20 69 73 20 6e 6f 20 70 65  n there is no pe
5a40: 6e 64 69 6e 67 20 62 79 74 65 2e 0a 2a 2f 0a 23  nding byte..*/.#
5a50: 69 66 64 65 66 20 53 51 4c 49 54 45 5f 4f 4d 49  ifdef SQLITE_OMI
5a60: 54 5f 44 49 53 4b 49 4f 0a 23 20 64 65 66 69 6e  T_DISKIO.# defin
5a70: 65 20 50 45 4e 44 49 4e 47 5f 42 59 54 45 5f 50  e PENDING_BYTE_P
5a80: 41 47 45 28 70 42 74 29 20 20 30 78 37 66 66 66  AGE(pBt)  0x7fff
5a90: 66 66 66 66 0a 23 65 6c 73 65 0a 23 20 64 65 66  ffff.#else.# def
5aa0: 69 6e 65 20 50 45 4e 44 49 4e 47 5f 42 59 54 45  ine PENDING_BYTE
5ab0: 5f 50 41 47 45 28 70 42 74 29 20 28 28 50 45 4e  _PAGE(pBt) ((PEN
5ac0: 44 49 4e 47 5f 42 59 54 45 2f 28 70 42 74 29 2d  DING_BYTE/(pBt)-
5ad0: 3e 70 61 67 65 53 69 7a 65 29 2b 31 29 0a 23 65  >pageSize)+1).#e
5ae0: 6e 64 69 66 0a 0a 2f 2a 0a 2a 2a 20 41 20 6c 69  ndif../*.** A li
5af0: 6e 6b 65 64 20 6c 69 73 74 20 6f 66 20 74 68 65  nked list of the
5b00: 20 66 6f 6c 6c 6f 77 69 6e 67 20 73 74 72 75 63   following struc
5b10: 74 75 72 65 73 20 69 73 20 73 74 6f 72 65 64 20  tures is stored 
5b20: 61 74 20 42 74 53 68 61 72 65 64 2e 70 4c 6f 63  at BtShared.pLoc
5b30: 6b 2e 0a 2a 2a 20 4c 6f 63 6b 73 20 61 72 65 20  k..** Locks are 
5b40: 61 64 64 65 64 20 28 6f 72 20 75 70 67 72 61 64  added (or upgrad
5b50: 65 64 20 66 72 6f 6d 20 52 45 41 44 5f 4c 4f 43  ed from READ_LOC
5b60: 4b 20 74 6f 20 57 52 49 54 45 5f 4c 4f 43 4b 29  K to WRITE_LOCK)
5b70: 20 77 68 65 6e 20 61 20 63 75 72 73 6f 72 20 0a   when a cursor .
5b80: 2a 2a 20 69 73 20 6f 70 65 6e 65 64 20 6f 6e 20  ** is opened on 
5b90: 74 68 65 20 74 61 62 6c 65 20 77 69 74 68 20 72  the table with r
5ba0: 6f 6f 74 20 70 61 67 65 20 42 74 53 68 61 72 65  oot page BtShare
5bb0: 64 2e 69 54 61 62 6c 65 2e 20 4c 6f 63 6b 73 20  d.iTable. Locks 
5bc0: 61 72 65 20 72 65 6d 6f 76 65 64 0a 2a 2a 20 66  are removed.** f
5bd0: 72 6f 6d 20 74 68 69 73 20 6c 69 73 74 20 77 68  rom this list wh
5be0: 65 6e 20 61 20 74 72 61 6e 73 61 63 74 69 6f 6e  en a transaction
5bf0: 20 69 73 20 63 6f 6d 6d 69 74 74 65 64 20 6f 72   is committed or
5c00: 20 72 6f 6c 6c 65 64 20 62 61 63 6b 2c 20 6f 72   rolled back, or
5c10: 20 77 68 65 6e 0a 2a 2a 20 61 20 62 74 72 65 65   when.** a btree
5c20: 20 68 61 6e 64 6c 65 20 69 73 20 63 6c 6f 73 65   handle is close
5c30: 64 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 42 74 4c  d..*/.struct BtL
5c40: 6f 63 6b 20 7b 0a 20 20 42 74 72 65 65 20 2a 70  ock {.  Btree *p
5c50: 42 74 72 65 65 3b 20 20 20 20 20 20 20 20 2f 2a  Btree;        /*
5c60: 20 42 74 72 65 65 20 68 61 6e 64 6c 65 20 68 6f   Btree handle ho
5c70: 6c 64 69 6e 67 20 74 68 69 73 20 6c 6f 63 6b 20  lding this lock 
5c80: 2a 2f 0a 20 20 50 67 6e 6f 20 69 54 61 62 6c 65  */.  Pgno iTable
5c90: 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 52 6f  ;          /* Ro
5ca0: 6f 74 20 70 61 67 65 20 6f 66 20 74 61 62 6c 65  ot page of table
5cb0: 20 2a 2f 0a 20 20 75 38 20 65 4c 6f 63 6b 3b 20   */.  u8 eLock; 
5cc0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 52              /* R
5cd0: 45 41 44 5f 4c 4f 43 4b 20 6f 72 20 57 52 49 54  EAD_LOCK or WRIT
5ce0: 45 5f 4c 4f 43 4b 20 2a 2f 0a 20 20 42 74 4c 6f  E_LOCK */.  BtLo
5cf0: 63 6b 20 2a 70 4e 65 78 74 3b 20 20 20 20 20 20  ck *pNext;      
5d00: 20 20 2f 2a 20 4e 65 78 74 20 69 6e 20 42 74 53    /* Next in BtS
5d10: 68 61 72 65 64 2e 70 4c 6f 63 6b 20 6c 69 73 74  hared.pLock list
5d20: 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 20 43 61 6e 64 69   */.};../* Candi
5d30: 64 61 74 65 20 76 61 6c 75 65 73 20 66 6f 72 20  date values for 
5d40: 42 74 4c 6f 63 6b 2e 65 4c 6f 63 6b 20 2a 2f 0a  BtLock.eLock */.
5d50: 23 64 65 66 69 6e 65 20 52 45 41 44 5f 4c 4f 43  #define READ_LOC
5d60: 4b 20 20 20 20 20 31 0a 23 64 65 66 69 6e 65 20  K     1.#define 
5d70: 57 52 49 54 45 5f 4c 4f 43 4b 20 20 20 20 32 0a  WRITE_LOCK    2.
5d80: 0a 2f 2a 0a 2a 2a 20 54 68 65 73 65 20 6d 61 63  ./*.** These mac
5d90: 72 6f 73 20 64 65 66 69 6e 65 20 74 68 65 20 6c  ros define the l
5da0: 6f 63 61 74 69 6f 6e 20 6f 66 20 74 68 65 20 70  ocation of the p
5db0: 6f 69 6e 74 65 72 2d 6d 61 70 20 65 6e 74 72 79  ointer-map entry
5dc0: 20 66 6f 72 20 61 20 0a 2a 2a 20 64 61 74 61 62   for a .** datab
5dd0: 61 73 65 20 70 61 67 65 2e 20 54 68 65 20 66 69  ase page. The fi
5de0: 72 73 74 20 61 72 67 75 6d 65 6e 74 20 74 6f 20  rst argument to 
5df0: 65 61 63 68 20 69 73 20 74 68 65 20 6e 75 6d 62  each is the numb
5e00: 65 72 20 6f 66 20 75 73 61 62 6c 65 0a 2a 2a 20  er of usable.** 
5e10: 62 79 74 65 73 20 6f 6e 20 65 61 63 68 20 70 61  bytes on each pa
5e20: 67 65 20 6f 66 20 74 68 65 20 64 61 74 61 62 61  ge of the databa
5e30: 73 65 20 28 6f 66 74 65 6e 20 31 30 32 34 29 2e  se (often 1024).
5e40: 20 54 68 65 20 73 65 63 6f 6e 64 20 69 73 20 74   The second is t
5e50: 68 65 0a 2a 2a 20 70 61 67 65 20 6e 75 6d 62 65  he.** page numbe
5e60: 72 20 74 6f 20 6c 6f 6f 6b 20 75 70 20 69 6e 20  r to look up in 
5e70: 74 68 65 20 70 6f 69 6e 74 65 72 20 6d 61 70 2e  the pointer map.
5e80: 0a 2a 2a 0a 2a 2a 20 50 54 52 4d 41 50 5f 50 41  .**.** PTRMAP_PA
5e90: 47 45 4e 4f 20 72 65 74 75 72 6e 73 20 74 68 65  GENO returns the
5ea0: 20 64 61 74 61 62 61 73 65 20 70 61 67 65 20 6e   database page n
5eb0: 75 6d 62 65 72 20 6f 66 20 74 68 65 20 70 6f 69  umber of the poi
5ec0: 6e 74 65 72 2d 6d 61 70 0a 2a 2a 20 70 61 67 65  nter-map.** page
5ed0: 20 74 68 61 74 20 73 74 6f 72 65 73 20 74 68 65   that stores the
5ee0: 20 72 65 71 75 69 72 65 64 20 70 6f 69 6e 74 65   required pointe
5ef0: 72 2e 20 50 54 52 4d 41 50 5f 50 54 52 4f 46 46  r. PTRMAP_PTROFF
5f00: 53 45 54 20 72 65 74 75 72 6e 73 0a 2a 2a 20 74  SET returns.** t
5f10: 68 65 20 6f 66 66 73 65 74 20 6f 66 20 74 68 65  he offset of the
5f20: 20 72 65 71 75 65 73 74 65 64 20 6d 61 70 20 65   requested map e
5f30: 6e 74 72 79 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 74  ntry..**.** If t
5f40: 68 65 20 70 67 6e 6f 20 61 72 67 75 6d 65 6e 74  he pgno argument
5f50: 20 70 61 73 73 65 64 20 74 6f 20 50 54 52 4d 41   passed to PTRMA
5f60: 50 5f 50 41 47 45 4e 4f 20 69 73 20 61 20 70 6f  P_PAGENO is a po
5f70: 69 6e 74 65 72 2d 6d 61 70 20 70 61 67 65 2c 0a  inter-map page,.
5f80: 2a 2a 20 74 68 65 6e 20 70 67 6e 6f 20 69 73 20  ** then pgno is 
5f90: 72 65 74 75 72 6e 65 64 2e 20 53 6f 20 28 70 67  returned. So (pg
5fa0: 6e 6f 3d 3d 50 54 52 4d 41 50 5f 50 41 47 45 4e  no==PTRMAP_PAGEN
5fb0: 4f 28 70 67 73 7a 2c 20 70 67 6e 6f 29 29 20 63  O(pgsz, pgno)) c
5fc0: 61 6e 20 62 65 0a 2a 2a 20 75 73 65 64 20 74 6f  an be.** used to
5fd0: 20 74 65 73 74 20 69 66 20 70 67 6e 6f 20 69 73   test if pgno is
5fe0: 20 61 20 70 6f 69 6e 74 65 72 2d 6d 61 70 20 70   a pointer-map p
5ff0: 61 67 65 2e 20 50 54 52 4d 41 50 5f 49 53 50 41  age. PTRMAP_ISPA
6000: 47 45 20 69 6d 70 6c 65 6d 65 6e 74 73 0a 2a 2a  GE implements.**
6010: 20 74 68 69 73 20 74 65 73 74 2e 0a 2a 2f 0a 23   this test..*/.#
6020: 64 65 66 69 6e 65 20 50 54 52 4d 41 50 5f 50 41  define PTRMAP_PA
6030: 47 45 4e 4f 28 70 42 74 2c 20 70 67 6e 6f 29 20  GENO(pBt, pgno) 
6040: 70 74 72 6d 61 70 50 61 67 65 6e 6f 28 70 42 74  ptrmapPageno(pBt
6050: 2c 20 70 67 6e 6f 29 0a 23 64 65 66 69 6e 65 20  , pgno).#define 
6060: 50 54 52 4d 41 50 5f 50 54 52 4f 46 46 53 45 54  PTRMAP_PTROFFSET
6070: 28 70 42 74 2c 20 70 67 6e 6f 29 20 28 35 2a 28  (pBt, pgno) (5*(
6080: 70 67 6e 6f 2d 70 74 72 6d 61 70 50 61 67 65 6e  pgno-ptrmapPagen
6090: 6f 28 70 42 74 2c 20 70 67 6e 6f 29 2d 31 29 29  o(pBt, pgno)-1))
60a0: 0a 23 64 65 66 69 6e 65 20 50 54 52 4d 41 50 5f  .#define PTRMAP_
60b0: 49 53 50 41 47 45 28 70 42 74 2c 20 70 67 6e 6f  ISPAGE(pBt, pgno
60c0: 29 20 28 50 54 52 4d 41 50 5f 50 41 47 45 4e 4f  ) (PTRMAP_PAGENO
60d0: 28 28 70 42 74 29 2c 28 70 67 6e 6f 29 29 3d 3d  ((pBt),(pgno))==
60e0: 28 70 67 6e 6f 29 29 0a 0a 2f 2a 0a 2a 2a 20 54  (pgno))../*.** T
60f0: 68 65 20 70 6f 69 6e 74 65 72 20 6d 61 70 20 69  he pointer map i
6100: 73 20 61 20 6c 6f 6f 6b 75 70 20 74 61 62 6c 65  s a lookup table
6110: 20 74 68 61 74 20 69 64 65 6e 74 69 66 69 65 73   that identifies
6120: 20 74 68 65 20 70 61 72 65 6e 74 20 70 61 67 65   the parent page
6130: 20 66 6f 72 0a 2a 2a 20 65 61 63 68 20 63 68 69   for.** each chi
6140: 6c 64 20 70 61 67 65 20 69 6e 20 74 68 65 20 64  ld page in the d
6150: 61 74 61 62 61 73 65 20 66 69 6c 65 2e 20 20 54  atabase file.  T
6160: 68 65 20 70 61 72 65 6e 74 20 70 61 67 65 20 69  he parent page i
6170: 73 20 74 68 65 20 70 61 67 65 20 74 68 61 74 0a  s the page that.
6180: 2a 2a 20 63 6f 6e 74 61 69 6e 73 20 61 20 70 6f  ** contains a po
6190: 69 6e 74 65 72 20 74 6f 20 74 68 65 20 63 68 69  inter to the chi
61a0: 6c 64 2e 20 20 45 76 65 72 79 20 70 61 67 65 20  ld.  Every page 
61b0: 69 6e 20 74 68 65 20 64 61 74 61 62 61 73 65 20  in the database 
61c0: 63 6f 6e 74 61 69 6e 73 0a 2a 2a 20 30 20 6f 72  contains.** 0 or
61d0: 20 31 20 70 61 72 65 6e 74 20 70 61 67 65 73 2e   1 parent pages.
61e0: 20 20 28 49 6e 20 74 68 69 73 20 63 6f 6e 74 65    (In this conte
61f0: 78 74 20 27 64 61 74 61 62 61 73 65 20 70 61 67  xt 'database pag
6200: 65 27 20 72 65 66 65 72 73 0a 2a 2a 20 74 6f 20  e' refers.** to 
6210: 61 6e 79 20 70 61 67 65 20 74 68 61 74 20 69 73  any page that is
6220: 20 6e 6f 74 20 70 61 72 74 20 6f 66 20 74 68 65   not part of the
6230: 20 70 6f 69 6e 74 65 72 20 6d 61 70 20 69 74 73   pointer map its
6240: 65 6c 66 2e 29 20 20 45 61 63 68 20 70 6f 69 6e  elf.)  Each poin
6250: 74 65 72 20 6d 61 70 0a 2a 2a 20 65 6e 74 72 79  ter map.** entry
6260: 20 63 6f 6e 73 69 73 74 73 20 6f 66 20 61 20 73   consists of a s
6270: 69 6e 67 6c 65 20 62 79 74 65 20 27 74 79 70 65  ingle byte 'type
6280: 27 20 61 6e 64 20 61 20 34 20 62 79 74 65 20 70  ' and a 4 byte p
6290: 61 72 65 6e 74 20 70 61 67 65 20 6e 75 6d 62 65  arent page numbe
62a0: 72 2e 0a 2a 2a 20 54 68 65 20 50 54 52 4d 41 50  r..** The PTRMAP
62b0: 5f 58 58 58 20 69 64 65 6e 74 69 66 69 65 72 73  _XXX identifiers
62c0: 20 62 65 6c 6f 77 20 61 72 65 20 74 68 65 20 76   below are the v
62d0: 61 6c 69 64 20 74 79 70 65 73 2e 0a 2a 2a 0a 2a  alid types..**.*
62e0: 2a 20 54 68 65 20 70 75 72 70 6f 73 65 20 6f 66  * The purpose of
62f0: 20 74 68 65 20 70 6f 69 6e 74 65 72 20 6d 61 70   the pointer map
6300: 20 69 73 20 74 6f 20 66 61 63 69 6c 69 74 79 20   is to facility 
6310: 6d 6f 76 69 6e 67 20 70 61 67 65 73 20 66 72 6f  moving pages fro
6320: 6d 20 6f 6e 65 0a 2a 2a 20 70 6f 73 69 74 69 6f  m one.** positio
6330: 6e 20 69 6e 20 74 68 65 20 66 69 6c 65 20 74 6f  n in the file to
6340: 20 61 6e 6f 74 68 65 72 20 61 73 20 70 61 72 74   another as part
6350: 20 6f 66 20 61 75 74 6f 76 61 63 75 75 6d 2e 20   of autovacuum. 
6360: 20 57 68 65 6e 20 61 20 70 61 67 65 0a 2a 2a 20   When a page.** 
6370: 69 73 20 6d 6f 76 65 64 2c 20 74 68 65 20 70 6f  is moved, the po
6380: 69 6e 74 65 72 20 69 6e 20 69 74 73 20 70 61 72  inter in its par
6390: 65 6e 74 20 6d 75 73 74 20 62 65 20 75 70 64 61  ent must be upda
63a0: 74 65 64 20 74 6f 20 70 6f 69 6e 74 20 74 6f 20  ted to point to 
63b0: 74 68 65 0a 2a 2a 20 6e 65 77 20 6c 6f 63 61 74  the.** new locat
63c0: 69 6f 6e 2e 20 20 54 68 65 20 70 6f 69 6e 74 65  ion.  The pointe
63d0: 72 20 6d 61 70 20 69 73 20 75 73 65 64 20 74 6f  r map is used to
63e0: 20 6c 6f 63 61 74 65 20 74 68 65 20 70 61 72 65   locate the pare
63f0: 6e 74 20 70 61 67 65 20 71 75 69 63 6b 6c 79 2e  nt page quickly.
6400: 0a 2a 2a 0a 2a 2a 20 50 54 52 4d 41 50 5f 52 4f  .**.** PTRMAP_RO
6410: 4f 54 50 41 47 45 3a 20 54 68 65 20 64 61 74 61  OTPAGE: The data
6420: 62 61 73 65 20 70 61 67 65 20 69 73 20 61 20 72  base page is a r
6430: 6f 6f 74 2d 70 61 67 65 2e 20 54 68 65 20 70 61  oot-page. The pa
6440: 67 65 2d 6e 75 6d 62 65 72 20 69 73 20 6e 6f 74  ge-number is not
6450: 0a 2a 2a 20 20 20 20 20 20 20 20 20 20 20 20 20  .**             
6460: 20 20 20 20 20 75 73 65 64 20 69 6e 20 74 68 69       used in thi
6470: 73 20 63 61 73 65 2e 0a 2a 2a 0a 2a 2a 20 50 54  s case..**.** PT
6480: 52 4d 41 50 5f 46 52 45 45 50 41 47 45 3a 20 54  RMAP_FREEPAGE: T
6490: 68 65 20 64 61 74 61 62 61 73 65 20 70 61 67 65  he database page
64a0: 20 69 73 20 61 6e 20 75 6e 75 73 65 64 20 28 66   is an unused (f
64b0: 72 65 65 29 20 70 61 67 65 2e 20 54 68 65 20 70  ree) page. The p
64c0: 61 67 65 2d 6e 75 6d 62 65 72 20 0a 2a 2a 20 20  age-number .**  
64d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
64e0: 69 73 20 6e 6f 74 20 75 73 65 64 20 69 6e 20 74  is not used in t
64f0: 68 69 73 20 63 61 73 65 2e 0a 2a 2a 0a 2a 2a 20  his case..**.** 
6500: 50 54 52 4d 41 50 5f 4f 56 45 52 46 4c 4f 57 31  PTRMAP_OVERFLOW1
6510: 3a 20 54 68 65 20 64 61 74 61 62 61 73 65 20 70  : The database p
6520: 61 67 65 20 69 73 20 74 68 65 20 66 69 72 73 74  age is the first
6530: 20 70 61 67 65 20 69 6e 20 61 20 6c 69 73 74 20   page in a list 
6540: 6f 66 20 0a 2a 2a 20 20 20 20 20 20 20 20 20 20  of .**          
6550: 20 20 20 20 20 20 20 20 20 6f 76 65 72 66 6c 6f           overflo
6560: 77 20 70 61 67 65 73 2e 20 54 68 65 20 70 61 67  w pages. The pag
6570: 65 20 6e 75 6d 62 65 72 20 69 64 65 6e 74 69 66  e number identif
6580: 69 65 73 20 74 68 65 20 70 61 67 65 20 74 68 61  ies the page tha
6590: 74 0a 2a 2a 20 20 20 20 20 20 20 20 20 20 20 20  t.**            
65a0: 20 20 20 20 20 20 20 63 6f 6e 74 61 69 6e 73 20         contains 
65b0: 74 68 65 20 63 65 6c 6c 20 77 69 74 68 20 61 20  the cell with a 
65c0: 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 69 73 20  pointer to this 
65d0: 6f 76 65 72 66 6c 6f 77 20 70 61 67 65 2e 0a 2a  overflow page..*
65e0: 2a 0a 2a 2a 20 50 54 52 4d 41 50 5f 4f 56 45 52  *.** PTRMAP_OVER
65f0: 46 4c 4f 57 32 3a 20 54 68 65 20 64 61 74 61 62  FLOW2: The datab
6600: 61 73 65 20 70 61 67 65 20 69 73 20 74 68 65 20  ase page is the 
6610: 73 65 63 6f 6e 64 20 6f 72 20 6c 61 74 65 72 20  second or later 
6620: 70 61 67 65 20 69 6e 20 61 20 6c 69 73 74 20 6f  page in a list o
6630: 66 0a 2a 2a 20 20 20 20 20 20 20 20 20 20 20 20  f.**            
6640: 20 20 20 20 20 20 20 6f 76 65 72 66 6c 6f 77 20         overflow 
6650: 70 61 67 65 73 2e 20 54 68 65 20 70 61 67 65 2d  pages. The page-
6660: 6e 75 6d 62 65 72 20 69 64 65 6e 74 69 66 69 65  number identifie
6670: 73 20 74 68 65 20 70 72 65 76 69 6f 75 73 0a 2a  s the previous.*
6680: 2a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  *               
6690: 20 20 20 20 70 61 67 65 20 69 6e 20 74 68 65 20      page in the 
66a0: 6f 76 65 72 66 6c 6f 77 20 70 61 67 65 20 6c 69  overflow page li
66b0: 73 74 2e 0a 2a 2a 0a 2a 2a 20 50 54 52 4d 41 50  st..**.** PTRMAP
66c0: 5f 42 54 52 45 45 3a 20 54 68 65 20 64 61 74 61  _BTREE: The data
66d0: 62 61 73 65 20 70 61 67 65 20 69 73 20 61 20 6e  base page is a n
66e0: 6f 6e 2d 72 6f 6f 74 20 62 74 72 65 65 20 70 61  on-root btree pa
66f0: 67 65 2e 20 54 68 65 20 70 61 67 65 20 6e 75 6d  ge. The page num
6700: 62 65 72 0a 2a 2a 20 20 20 20 20 20 20 20 20 20  ber.**          
6710: 20 20 20 20 20 69 64 65 6e 74 69 66 69 65 73 20       identifies 
6720: 74 68 65 20 70 61 72 65 6e 74 20 70 61 67 65 20  the parent page 
6730: 69 6e 20 74 68 65 20 62 74 72 65 65 2e 0a 2a 2f  in the btree..*/
6740: 0a 23 64 65 66 69 6e 65 20 50 54 52 4d 41 50 5f  .#define PTRMAP_
6750: 52 4f 4f 54 50 41 47 45 20 31 0a 23 64 65 66 69  ROOTPAGE 1.#defi
6760: 6e 65 20 50 54 52 4d 41 50 5f 46 52 45 45 50 41  ne PTRMAP_FREEPA
6770: 47 45 20 32 0a 23 64 65 66 69 6e 65 20 50 54 52  GE 2.#define PTR
6780: 4d 41 50 5f 4f 56 45 52 46 4c 4f 57 31 20 33 0a  MAP_OVERFLOW1 3.
6790: 23 64 65 66 69 6e 65 20 50 54 52 4d 41 50 5f 4f  #define PTRMAP_O
67a0: 56 45 52 46 4c 4f 57 32 20 34 0a 23 64 65 66 69  VERFLOW2 4.#defi
67b0: 6e 65 20 50 54 52 4d 41 50 5f 42 54 52 45 45 20  ne PTRMAP_BTREE 
67c0: 35 0a 0a 2f 2a 20 41 20 62 75 6e 63 68 20 6f 66  5../* A bunch of
67d0: 20 61 73 73 65 72 74 28 29 20 73 74 61 74 65 6d   assert() statem
67e0: 65 6e 74 73 20 74 6f 20 63 68 65 63 6b 20 74 68  ents to check th
67f0: 65 20 74 72 61 6e 73 61 63 74 69 6f 6e 20 73 74  e transaction st
6800: 61 74 65 20 76 61 72 69 61 62 6c 65 73 0a 2a 2a  ate variables.**
6810: 20 6f 66 20 68 61 6e 64 6c 65 20 70 20 28 74 79   of handle p (ty
6820: 70 65 20 42 74 72 65 65 2a 29 20 61 72 65 20 69  pe Btree*) are i
6830: 6e 74 65 72 6e 61 6c 6c 79 20 63 6f 6e 73 69 73  nternally consis
6840: 74 65 6e 74 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65  tent..*/.#define
6850: 20 62 74 72 65 65 49 6e 74 65 67 72 69 74 79 28   btreeIntegrity(
6860: 70 29 20 5c 0a 20 20 61 73 73 65 72 74 28 20 70  p) \.  assert( p
6870: 2d 3e 70 42 74 2d 3e 69 6e 54 72 61 6e 73 61 63  ->pBt->inTransac
6880: 74 69 6f 6e 21 3d 54 52 41 4e 53 5f 4e 4f 4e 45  tion!=TRANS_NONE
6890: 20 7c 7c 20 70 2d 3e 70 42 74 2d 3e 6e 54 72 61   || p->pBt->nTra
68a0: 6e 73 61 63 74 69 6f 6e 3d 3d 30 20 29 3b 20 5c  nsaction==0 ); \
68b0: 0a 20 20 61 73 73 65 72 74 28 20 70 2d 3e 70 42  .  assert( p->pB
68c0: 74 2d 3e 69 6e 54 72 61 6e 73 61 63 74 69 6f 6e  t->inTransaction
68d0: 3e 3d 70 2d 3e 69 6e 54 72 61 6e 73 20 29 3b 20  >=p->inTrans ); 
68e0: 0a 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 20 49 53 41  .../*.** The ISA
68f0: 55 54 4f 56 41 43 55 55 4d 20 6d 61 63 72 6f 20  UTOVACUUM macro 
6900: 69 73 20 75 73 65 64 20 77 69 74 68 69 6e 20 62  is used within b
6910: 61 6c 61 6e 63 65 5f 6e 6f 6e 72 6f 6f 74 28 29  alance_nonroot()
6920: 20 74 6f 20 64 65 74 65 72 6d 69 6e 65 0a 2a 2a   to determine.**
6930: 20 69 66 20 74 68 65 20 64 61 74 61 62 61 73 65   if the database
6940: 20 73 75 70 70 6f 72 74 73 20 61 75 74 6f 2d 76   supports auto-v
6950: 61 63 75 75 6d 20 6f 72 20 6e 6f 74 2e 20 42 65  acuum or not. Be
6960: 63 61 75 73 65 20 69 74 20 69 73 20 75 73 65 64  cause it is used
6970: 0a 2a 2a 20 77 69 74 68 69 6e 20 61 6e 20 65 78  .** within an ex
6980: 70 72 65 73 73 69 6f 6e 20 74 68 61 74 20 69 73  pression that is
6990: 20 61 6e 20 61 72 67 75 6d 65 6e 74 20 74 6f 20   an argument to 
69a0: 61 6e 6f 74 68 65 72 20 6d 61 63 72 6f 20 0a 2a  another macro .*
69b0: 2a 20 28 73 71 6c 69 74 65 4d 61 6c 6c 6f 63 52  * (sqliteMallocR
69c0: 61 77 29 2c 20 69 74 20 69 73 20 6e 6f 74 20 70  aw), it is not p
69d0: 6f 73 73 69 62 6c 65 20 74 6f 20 75 73 65 20 63  ossible to use c
69e0: 6f 6e 64 69 74 69 6f 6e 61 6c 20 63 6f 6d 70 69  onditional compi
69f0: 6c 61 74 69 6f 6e 2e 0a 2a 2a 20 53 6f 2c 20 74  lation..** So, t
6a00: 68 69 73 20 6d 61 63 72 6f 20 69 73 20 64 65 66  his macro is def
6a10: 69 6e 65 64 20 69 6e 73 74 65 61 64 2e 0a 2a 2f  ined instead..*/
6a20: 0a 23 69 66 6e 64 65 66 20 53 51 4c 49 54 45 5f  .#ifndef SQLITE_
6a30: 4f 4d 49 54 5f 41 55 54 4f 56 41 43 55 55 4d 0a  OMIT_AUTOVACUUM.
6a40: 23 64 65 66 69 6e 65 20 49 53 41 55 54 4f 56 41  #define ISAUTOVA
6a50: 43 55 55 4d 20 28 70 42 74 2d 3e 61 75 74 6f 56  CUUM (pBt->autoV
6a60: 61 63 75 75 6d 29 0a 23 65 6c 73 65 0a 23 64 65  acuum).#else.#de
6a70: 66 69 6e 65 20 49 53 41 55 54 4f 56 41 43 55 55  fine ISAUTOVACUU
6a80: 4d 20 30 0a 23 65 6e 64 69 66 0a 0a 0a 2f 2a 0a  M 0.#endif.../*.
6a90: 2a 2a 20 54 68 69 73 20 73 74 72 75 63 74 75 72  ** This structur
6aa0: 65 20 69 73 20 70 61 73 73 65 64 20 61 72 6f 75  e is passed arou
6ab0: 6e 64 20 74 68 72 6f 75 67 68 20 61 6c 6c 20 74  nd through all t
6ac0: 68 65 20 73 61 6e 69 74 79 20 63 68 65 63 6b 69  he sanity checki
6ad0: 6e 67 20 72 6f 75 74 69 6e 65 73 0a 2a 2a 20 69  ng routines.** i
6ae0: 6e 20 6f 72 64 65 72 20 74 6f 20 6b 65 65 70 20  n order to keep 
6af0: 74 72 61 63 6b 20 6f 66 20 73 6f 6d 65 20 67 6c  track of some gl
6b00: 6f 62 61 6c 20 73 74 61 74 65 20 69 6e 66 6f 72  obal state infor
6b10: 6d 61 74 69 6f 6e 2e 0a 2a 2f 0a 74 79 70 65 64  mation..*/.typed
6b20: 65 66 20 73 74 72 75 63 74 20 49 6e 74 65 67 72  ef struct Integr
6b30: 69 74 79 43 6b 20 49 6e 74 65 67 72 69 74 79 43  ityCk IntegrityC
6b40: 6b 3b 0a 73 74 72 75 63 74 20 49 6e 74 65 67 72  k;.struct Integr
6b50: 69 74 79 43 6b 20 7b 0a 20 20 42 74 53 68 61 72  ityCk {.  BtShar
6b60: 65 64 20 2a 70 42 74 3b 20 20 20 20 2f 2a 20 54  ed *pBt;    /* T
6b70: 68 65 20 74 72 65 65 20 62 65 69 6e 67 20 63 68  he tree being ch
6b80: 65 63 6b 65 64 20 6f 75 74 20 2a 2f 0a 20 20 50  ecked out */.  P
6b90: 61 67 65 72 20 2a 70 50 61 67 65 72 3b 20 20 20  ager *pPager;   
6ba0: 20 2f 2a 20 54 68 65 20 61 73 73 6f 63 69 61 74   /* The associat
6bb0: 65 64 20 70 61 67 65 72 2e 20 20 41 6c 73 6f 20  ed pager.  Also 
6bc0: 61 63 63 65 73 73 69 62 6c 65 20 62 79 20 70 42  accessible by pB
6bd0: 74 2d 3e 70 50 61 67 65 72 20 2a 2f 0a 20 20 69  t->pPager */.  i
6be0: 6e 74 20 6e 50 61 67 65 3b 20 20 20 20 20 20 20  nt nPage;       
6bf0: 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 70 61   /* Number of pa
6c00: 67 65 73 20 69 6e 20 74 68 65 20 64 61 74 61 62  ges in the datab
6c10: 61 73 65 20 2a 2f 0a 20 20 69 6e 74 20 2a 61 6e  ase */.  int *an
6c20: 52 65 66 3b 20 20 20 20 20 20 20 2f 2a 20 4e 75  Ref;       /* Nu
6c30: 6d 62 65 72 20 6f 66 20 74 69 6d 65 73 20 65 61  mber of times ea
6c40: 63 68 20 70 61 67 65 20 69 73 20 72 65 66 65 72  ch page is refer
6c50: 65 6e 63 65 64 20 2a 2f 0a 20 20 69 6e 74 20 6d  enced */.  int m
6c60: 78 45 72 72 3b 20 20 20 20 20 20 20 20 2f 2a 20  xErr;        /* 
6c70: 53 74 6f 70 20 61 63 63 75 6d 75 6c 61 74 69 6e  Stop accumulatin
6c80: 67 20 65 72 72 6f 72 73 20 77 68 65 6e 20 74 68  g errors when th
6c90: 69 73 20 72 65 61 63 68 65 73 20 7a 65 72 6f 20  is reaches zero 
6ca0: 2a 2f 0a 20 20 63 68 61 72 20 2a 7a 45 72 72 4d  */.  char *zErrM
6cb0: 73 67 3b 20 20 20 20 2f 2a 20 41 6e 20 65 72 72  sg;    /* An err
6cc0: 6f 72 20 6d 65 73 73 61 67 65 2e 20 20 4e 55 4c  or message.  NUL
6cd0: 4c 20 69 66 20 6e 6f 20 65 72 72 6f 72 73 20 73  L if no errors s
6ce0: 65 65 6e 2e 20 2a 2f 0a 20 20 69 6e 74 20 6e 45  een. */.  int nE
6cf0: 72 72 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 4e  rr;         /* N
6d00: 75 6d 62 65 72 20 6f 66 20 6d 65 73 73 61 67 65  umber of message
6d10: 73 20 77 72 69 74 74 65 6e 20 74 6f 20 7a 45 72  s written to zEr
6d20: 72 4d 73 67 20 73 6f 20 66 61 72 20 2a 2f 0a 7d  rMsg so far */.}
6d30: 3b 0a 0a 2f 2a 0a 2a 2a 20 52 65 61 64 20 6f 72  ;../*.** Read or
6d40: 20 77 72 69 74 65 20 61 20 74 77 6f 2d 20 61 6e   write a two- an
6d50: 64 20 66 6f 75 72 2d 62 79 74 65 20 62 69 67 2d  d four-byte big-
6d60: 65 6e 64 69 61 6e 20 69 6e 74 65 67 65 72 20 76  endian integer v
6d70: 61 6c 75 65 73 2e 0a 2a 2f 0a 23 64 65 66 69 6e  alues..*/.#defin
6d80: 65 20 67 65 74 32 62 79 74 65 28 78 29 20 20 20  e get2byte(x)   
6d90: 28 28 78 29 5b 30 5d 3c 3c 38 20 7c 20 28 78 29  ((x)[0]<<8 | (x)
6da0: 5b 31 5d 29 0a 23 64 65 66 69 6e 65 20 70 75 74  [1]).#define put
6db0: 32 62 79 74 65 28 70 2c 76 29 20 28 28 70 29 5b  2byte(p,v) ((p)[
6dc0: 30 5d 20 3d 20 28 76 29 3e 3e 38 2c 20 28 70 29  0] = (v)>>8, (p)
6dd0: 5b 31 5d 20 3d 20 28 76 29 29 0a 23 64 65 66 69  [1] = (v)).#defi
6de0: 6e 65 20 67 65 74 34 62 79 74 65 20 73 71 6c 69  ne get4byte sqli
6df0: 74 65 33 47 65 74 34 62 79 74 65 0a 23 64 65 66  te3Get4byte.#def
6e00: 69 6e 65 20 70 75 74 34 62 79 74 65 20 73 71 6c  ine put4byte sql
6e10: 69 74 65 33 50 75 74 34 62 79 74 65 0a 0a 2f 2a  ite3Put4byte../*
6e20: 0a 2a 2a 20 49 6e 74 65 72 6e 61 6c 20 72 6f 75  .** Internal rou
6e30: 74 69 6e 65 73 20 74 68 61 74 20 73 68 6f 75 6c  tines that shoul
6e40: 64 20 62 65 20 61 63 63 65 73 73 65 64 20 62 79  d be accessed by
6e50: 20 74 68 65 20 62 74 72 65 65 20 6c 61 79 65 72   the btree layer
6e60: 20 6f 6e 6c 79 2e 0a 2a 2f 0a 69 6e 74 20 73 71   only..*/.int sq
6e70: 6c 69 74 65 33 42 74 72 65 65 47 65 74 50 61 67  lite3BtreeGetPag
6e80: 65 28 42 74 53 68 61 72 65 64 2a 2c 20 50 67 6e  e(BtShared*, Pgn
6e90: 6f 2c 20 4d 65 6d 50 61 67 65 2a 2a 2c 20 69 6e  o, MemPage**, in
6ea0: 74 29 3b 0a 69 6e 74 20 73 71 6c 69 74 65 33 42  t);.int sqlite3B
6eb0: 74 72 65 65 49 6e 69 74 50 61 67 65 28 4d 65 6d  treeInitPage(Mem
6ec0: 50 61 67 65 20 2a 70 50 61 67 65 2c 20 4d 65 6d  Page *pPage, Mem
6ed0: 50 61 67 65 20 2a 70 50 61 72 65 6e 74 29 3b 0a  Page *pParent);.
6ee0: 76 6f 69 64 20 73 71 6c 69 74 65 33 42 74 72 65  void sqlite3Btre
6ef0: 65 50 61 72 73 65 43 65 6c 6c 50 74 72 28 4d 65  eParseCellPtr(Me
6f00: 6d 50 61 67 65 2a 2c 20 75 38 2a 2c 20 43 65 6c  mPage*, u8*, Cel
6f10: 6c 49 6e 66 6f 2a 29 3b 0a 76 6f 69 64 20 73 71  lInfo*);.void sq
6f20: 6c 69 74 65 33 42 74 72 65 65 50 61 72 73 65 43  lite3BtreeParseC
6f30: 65 6c 6c 28 4d 65 6d 50 61 67 65 2a 2c 20 69 6e  ell(MemPage*, in
6f40: 74 2c 20 43 65 6c 6c 49 6e 66 6f 2a 29 3b 0a 23  t, CellInfo*);.#
6f50: 69 66 64 65 66 20 53 51 4c 49 54 45 5f 54 45 53  ifdef SQLITE_TES
6f60: 54 0a 75 38 20 2a 73 71 6c 69 74 65 33 42 74 72  T.u8 *sqlite3Btr
6f70: 65 65 46 69 6e 64 43 65 6c 6c 28 4d 65 6d 50 61  eeFindCell(MemPa
6f80: 67 65 20 2a 70 50 61 67 65 2c 20 69 6e 74 20 69  ge *pPage, int i
6f90: 43 65 6c 6c 29 3b 0a 23 65 6e 64 69 66 0a 69 6e  Cell);.#endif.in
6fa0: 74 20 73 71 6c 69 74 65 33 42 74 72 65 65 52 65  t sqlite3BtreeRe
6fb0: 73 74 6f 72 65 4f 72 43 6c 65 61 72 43 75 72 73  storeOrClearCurs
6fc0: 6f 72 50 6f 73 69 74 69 6f 6e 28 42 74 43 75 72  orPosition(BtCur
6fd0: 73 6f 72 20 2a 70 43 75 72 29 3b 0a 76 6f 69 64  sor *pCur);.void
6fe0: 20 73 71 6c 69 74 65 33 42 74 72 65 65 47 65 74   sqlite3BtreeGet
6ff0: 54 65 6d 70 43 75 72 73 6f 72 28 42 74 43 75 72  TempCursor(BtCur
7000: 73 6f 72 20 2a 70 43 75 72 2c 20 42 74 43 75 72  sor *pCur, BtCur
7010: 73 6f 72 20 2a 70 54 65 6d 70 43 75 72 29 3b 0a  sor *pTempCur);.
7020: 76 6f 69 64 20 73 71 6c 69 74 65 33 42 74 72 65  void sqlite3Btre
7030: 65 52 65 6c 65 61 73 65 54 65 6d 70 43 75 72 73  eReleaseTempCurs
7040: 6f 72 28 42 74 43 75 72 73 6f 72 20 2a 70 43 75  or(BtCursor *pCu
7050: 72 29 3b 0a 69 6e 74 20 73 71 6c 69 74 65 33 42  r);.int sqlite3B
7060: 74 72 65 65 49 73 52 6f 6f 74 50 61 67 65 28 4d  treeIsRootPage(M
7070: 65 6d 50 61 67 65 20 2a 70 50 61 67 65 29 3b 0a  emPage *pPage);.
7080: 76 6f 69 64 20 73 71 6c 69 74 65 33 42 74 72 65  void sqlite3Btre
7090: 65 4d 6f 76 65 54 6f 50 61 72 65 6e 74 28 42 74  eMoveToParent(Bt
70a0: 43 75 72 73 6f 72 20 2a 70 43 75 72 29 3b 0a     Cursor *pCur);.