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