0000: 2f 2a 0a 2a 2a 20 32 30 30 34 20 41 70 72 69 6c /*.** 2004 April
0010: 20 36 0a 2a 2a 0a 2a 2a 20 54 68 65 20 61 75 74 6.**.** The aut
0020: 68 6f 72 20 64 69 73 63 6c 61 69 6d 73 20 63 6f hor disclaims co
0030: 70 79 72 69 67 68 74 20 74 6f 20 74 68 69 73 20 pyright to this
0040: 73 6f 75 72 63 65 20 63 6f 64 65 2e 20 20 49 6e source code. In
0050: 20 70 6c 61 63 65 20 6f 66 0a 2a 2a 20 61 20 6c place of.** a l
0060: 65 67 61 6c 20 6e 6f 74 69 63 65 2c 20 68 65 72 egal notice, her
0070: 65 20 69 73 20 61 20 62 6c 65 73 73 69 6e 67 3a e is a blessing:
0080: 0a 2a 2a 0a 2a 2a 20 20 20 20 4d 61 79 20 79 6f .**.** May yo
0090: 75 20 64 6f 20 67 6f 6f 64 20 61 6e 64 20 6e 6f u do good and no
00a0: 74 20 65 76 69 6c 2e 0a 2a 2a 20 20 20 20 4d 61 t evil..** Ma
00b0: 79 20 79 6f 75 20 66 69 6e 64 20 66 6f 72 67 69 y you find forgi
00c0: 76 65 6e 65 73 73 20 66 6f 72 20 79 6f 75 72 73 veness for yours
00d0: 65 6c 66 20 61 6e 64 20 66 6f 72 67 69 76 65 20 elf and forgive
00e0: 6f 74 68 65 72 73 2e 0a 2a 2a 20 20 20 20 4d 61 others..** Ma
00f0: 79 20 79 6f 75 20 73 68 61 72 65 20 66 72 65 65 y you share free
0100: 6c 79 2c 20 6e 65 76 65 72 20 74 61 6b 69 6e 67 ly, never taking
0110: 20 6d 6f 72 65 20 74 68 61 6e 20 79 6f 75 20 67 more than you g
0120: 69 76 65 2e 0a 2a 2a 0a 2a 2a 2a 2a 2a 2a 2a 2a ive..**.********
0130: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0140: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0150: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0160: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a ****************
0170: 2a 0a 2a 2a 20 24 49 64 3a 20 62 74 72 65 65 49 *.** $Id: btreeI
0180: 6e 74 2e 68 2c 76 20 31 2e 31 30 20 32 30 30 37 nt.h,v 1.10 2007
0190: 2f 30 38 2f 32 37 20 32 31 3a 34 39 3a 33 34 20 /08/27 21:49:34
01a0: 64 72 68 20 45 78 70 20 24 0a 2a 2a 0a 2a 2a 20 drh Exp $.**.**
01b0: 54 68 69 73 20 66 69 6c 65 20 69 6d 70 6c 65 6d This file implem
01c0: 65 6e 74 73 20 61 20 65 78 74 65 72 6e 61 6c 20 ents a external
01d0: 28 64 69 73 6b 2d 62 61 73 65 64 29 20 64 61 74 (disk-based) dat
01e0: 61 62 61 73 65 20 75 73 69 6e 67 20 42 54 72 65 abase using BTre
01f0: 65 73 2e 0a 2a 2a 20 46 6f 72 20 61 20 64 65 74 es..** For a det
0200: 61 69 6c 65 64 20 64 69 73 63 75 73 73 69 6f 6e ailed discussion
0210: 20 6f 66 20 42 54 72 65 65 73 2c 20 72 65 66 65 of BTrees, refe
0220: 72 20 74 6f 0a 2a 2a 0a 2a 2a 20 20 20 20 20 44 r to.**.** D
0230: 6f 6e 61 6c 64 20 45 2e 20 4b 6e 75 74 68 2c 20 onald E. Knuth,
0240: 54 48 45 20 41 52 54 20 4f 46 20 43 4f 4d 50 55 THE ART OF COMPU
0250: 54 45 52 20 50 52 4f 47 52 41 4d 4d 49 4e 47 2c TER PROGRAMMING,
0260: 20 56 6f 6c 75 6d 65 20 33 3a 0a 2a 2a 20 20 20 Volume 3:.**
0270: 20 20 22 53 6f 72 74 69 6e 67 20 41 6e 64 20 53 "Sorting And S
0280: 65 61 72 63 68 69 6e 67 22 2c 20 70 61 67 65 73 earching", pages
0290: 20 34 37 33 2d 34 38 30 2e 20 41 64 64 69 73 6f 473-480. Addiso
02a0: 6e 2d 57 65 73 6c 65 79 0a 2a 2a 20 20 20 20 20 n-Wesley.**
02b0: 50 75 62 6c 69 73 68 69 6e 67 20 43 6f 6d 70 61 Publishing Compa
02c0: 6e 79 2c 20 52 65 61 64 69 6e 67 2c 20 4d 61 73 ny, Reading, Mas
02d0: 73 61 63 68 75 73 65 74 74 73 2e 0a 2a 2a 0a 2a sachusetts..**.*
02e0: 2a 20 54 68 65 20 62 61 73 69 63 20 69 64 65 61 * The basic idea
02f0: 20 69 73 20 74 68 61 74 20 65 61 63 68 20 70 61 is that each pa
0300: 67 65 20 6f 66 20 74 68 65 20 66 69 6c 65 20 63 ge of the file c
0310: 6f 6e 74 61 69 6e 73 20 4e 20 64 61 74 61 62 61 ontains N databa
0320: 73 65 0a 2a 2a 20 65 6e 74 72 69 65 73 20 61 6e se.** entries an
0330: 64 20 4e 2b 31 20 70 6f 69 6e 74 65 72 73 20 74 d N+1 pointers t
0340: 6f 20 73 75 62 70 61 67 65 73 2e 0a 2a 2a 0a 2a o subpages..**.*
0350: 2a 20 20 20 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d * ------------
0360: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0370: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0380: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0390: 2d 2d 2d 2d 0a 2a 2a 20 20 20 7c 20 20 50 74 72 ----.** | Ptr
03a0: 28 30 29 20 7c 20 4b 65 79 28 30 29 20 7c 20 50 (0) | Key(0) | P
03b0: 74 72 28 31 29 20 7c 20 4b 65 79 28 31 29 20 7c tr(1) | Key(1) |
03c0: 20 2e 2e 2e 20 7c 20 4b 65 79 28 4e 2d 31 29 20 ... | Key(N-1)
03d0: 7c 20 50 74 72 28 4e 29 20 7c 0a 2a 2a 20 20 20 | Ptr(N) |.**
03e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
03f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0400: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0410: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0420: 0a 2a 2a 0a 2a 2a 20 41 6c 6c 20 6f 66 20 74 68 .**.** All of th
0430: 65 20 6b 65 79 73 20 6f 6e 20 74 68 65 20 70 61 e keys on the pa
0440: 67 65 20 74 68 61 74 20 50 74 72 28 30 29 20 70 ge that Ptr(0) p
0450: 6f 69 6e 74 73 20 74 6f 20 68 61 76 65 20 76 61 oints to have va
0460: 6c 75 65 73 20 6c 65 73 73 0a 2a 2a 20 74 68 61 lues less.** tha
0470: 6e 20 4b 65 79 28 30 29 2e 20 20 41 6c 6c 20 6f n Key(0). All o
0480: 66 20 74 68 65 20 6b 65 79 73 20 6f 6e 20 70 61 f the keys on pa
0490: 67 65 20 50 74 72 28 31 29 20 61 6e 64 20 69 74 ge Ptr(1) and it
04a0: 73 20 73 75 62 70 61 67 65 73 20 68 61 76 65 0a s subpages have.
04b0: 2a 2a 20 76 61 6c 75 65 73 20 67 72 65 61 74 65 ** values greate
04c0: 72 20 74 68 61 6e 20 4b 65 79 28 30 29 20 61 6e r than Key(0) an
04d0: 64 20 6c 65 73 73 20 74 68 61 6e 20 4b 65 79 28 d less than Key(
04e0: 31 29 2e 20 20 41 6c 6c 20 6f 66 20 74 68 65 20 1). All of the
04f0: 6b 65 79 73 0a 2a 2a 20 6f 6e 20 50 74 72 28 4e keys.** on Ptr(N
0500: 29 20 61 6e 64 20 69 74 73 20 73 75 62 70 61 67 ) and its subpag
0510: 65 73 20 68 61 76 65 20 76 61 6c 75 65 73 20 67 es have values g
0520: 72 65 61 74 65 72 20 74 68 61 6e 20 4b 65 79 28 reater than Key(
0530: 4e 2d 31 29 2e 20 20 41 6e 64 0a 2a 2a 20 73 6f N-1). And.** so
0540: 20 66 6f 72 74 68 2e 0a 2a 2a 0a 2a 2a 20 46 69 forth..**.** Fi
0550: 6e 64 69 6e 67 20 61 20 70 61 72 74 69 63 75 6c nding a particul
0560: 61 72 20 6b 65 79 20 72 65 71 75 69 72 65 73 20 ar key requires
0570: 72 65 61 64 69 6e 67 20 4f 28 6c 6f 67 28 4d 29 reading O(log(M)
0580: 29 20 70 61 67 65 73 20 66 72 6f 6d 20 74 68 65 ) pages from the
0590: 20 0a 2a 2a 20 64 69 73 6b 20 77 68 65 72 65 20 .** disk where
05a0: 4d 20 69 73 20 74 68 65 20 6e 75 6d 62 65 72 20 M is the number
05b0: 6f 66 20 65 6e 74 72 69 65 73 20 69 6e 20 74 68 of entries in th
05c0: 65 20 74 72 65 65 2e 0a 2a 2a 0a 2a 2a 20 49 6e e tree..**.** In
05d0: 20 74 68 69 73 20 69 6d 70 6c 65 6d 65 6e 74 61 this implementa
05e0: 74 69 6f 6e 2c 20 61 20 73 69 6e 67 6c 65 20 66 tion, a single f
05f0: 69 6c 65 20 63 61 6e 20 68 6f 6c 64 20 6f 6e 65 ile can hold one
0600: 20 6f 72 20 6d 6f 72 65 20 73 65 70 61 72 61 74 or more separat
0610: 65 20 0a 2a 2a 20 42 54 72 65 65 73 2e 20 20 45 e .** BTrees. E
0620: 61 63 68 20 42 54 72 65 65 20 69 73 20 69 64 65 ach BTree is ide
0630: 6e 74 69 66 69 65 64 20 62 79 20 74 68 65 20 69 ntified by the i
0640: 6e 64 65 78 20 6f 66 20 69 74 73 20 72 6f 6f 74 ndex of its root
0650: 20 70 61 67 65 2e 20 20 54 68 65 0a 2a 2a 20 6b page. The.** k
0660: 65 79 20 61 6e 64 20 64 61 74 61 20 66 6f 72 20 ey and data for
0670: 61 6e 79 20 65 6e 74 72 79 20 61 72 65 20 63 6f any entry are co
0680: 6d 62 69 6e 65 64 20 74 6f 20 66 6f 72 6d 20 74 mbined to form t
0690: 68 65 20 22 70 61 79 6c 6f 61 64 22 2e 20 20 41 he "payload". A
06a0: 0a 2a 2a 20 66 69 78 65 64 20 61 6d 6f 75 6e 74 .** fixed amount
06b0: 20 6f 66 20 70 61 79 6c 6f 61 64 20 63 61 6e 20 of payload can
06c0: 62 65 20 63 61 72 72 69 65 64 20 64 69 72 65 63 be carried direc
06d0: 74 6c 79 20 6f 6e 20 74 68 65 20 64 61 74 61 62 tly on the datab
06e0: 61 73 65 0a 2a 2a 20 70 61 67 65 2e 20 20 49 66 ase.** page. If
06f0: 20 74 68 65 20 70 61 79 6c 6f 61 64 20 69 73 20 the payload is
0700: 6c 61 72 67 65 72 20 74 68 61 6e 20 74 68 65 20 larger than the
0710: 70 72 65 73 65 74 20 61 6d 6f 75 6e 74 20 74 68 preset amount th
0720: 65 6e 20 73 75 72 70 6c 75 73 0a 2a 2a 20 62 79 en surplus.** by
0730: 74 65 73 20 61 72 65 20 73 74 6f 72 65 64 20 6f tes are stored o
0740: 6e 20 6f 76 65 72 66 6c 6f 77 20 70 61 67 65 73 n overflow pages
0750: 2e 20 20 54 68 65 20 70 61 79 6c 6f 61 64 20 66 . The payload f
0760: 6f 72 20 61 6e 20 65 6e 74 72 79 0a 2a 2a 20 61 or an entry.** a
0770: 6e 64 20 74 68 65 20 70 72 65 63 65 64 69 6e 67 nd the preceding
0780: 20 70 6f 69 6e 74 65 72 20 61 72 65 20 63 6f 6d pointer are com
0790: 62 69 6e 65 64 20 74 6f 20 66 6f 72 6d 20 61 20 bined to form a
07a0: 22 43 65 6c 6c 22 2e 20 20 45 61 63 68 20 0a 2a "Cell". Each .*
07b0: 2a 20 70 61 67 65 20 68 61 73 20 61 20 73 6d 61 * page has a sma
07c0: 6c 6c 20 68 65 61 64 65 72 20 77 68 69 63 68 20 ll header which
07d0: 63 6f 6e 74 61 69 6e 73 20 74 68 65 20 50 74 72 contains the Ptr
07e0: 28 4e 29 20 70 6f 69 6e 74 65 72 20 61 6e 64 20 (N) pointer and
07f0: 6f 74 68 65 72 0a 2a 2a 20 69 6e 66 6f 72 6d 61 other.** informa
0800: 74 69 6f 6e 20 73 75 63 68 20 61 73 20 74 68 65 tion such as the
0810: 20 73 69 7a 65 20 6f 66 20 6b 65 79 20 61 6e 64 size of key and
0820: 20 64 61 74 61 2e 0a 2a 2a 0a 2a 2a 20 46 4f 52 data..**.** FOR
0830: 4d 41 54 20 44 45 54 41 49 4c 53 0a 2a 2a 0a 2a MAT DETAILS.**.*
0840: 2a 20 54 68 65 20 66 69 6c 65 20 69 73 20 64 69 * The file is di
0850: 76 69 64 65 64 20 69 6e 74 6f 20 70 61 67 65 73 vided into pages
0860: 2e 20 20 54 68 65 20 66 69 72 73 74 20 70 61 67 . The first pag
0870: 65 20 69 73 20 63 61 6c 6c 65 64 20 70 61 67 65 e is called page
0880: 20 31 2c 0a 2a 2a 20 74 68 65 20 73 65 63 6f 6e 1,.** the secon
0890: 64 20 69 73 20 70 61 67 65 20 32 2c 20 61 6e 64 d is page 2, and
08a0: 20 73 6f 20 66 6f 72 74 68 2e 20 20 41 20 70 61 so forth. A pa
08b0: 67 65 20 6e 75 6d 62 65 72 20 6f 66 20 7a 65 72 ge number of zer
08c0: 6f 20 69 6e 64 69 63 61 74 65 73 0a 2a 2a 20 22 o indicates.** "
08d0: 6e 6f 20 73 75 63 68 20 70 61 67 65 22 2e 20 20 no such page".
08e0: 54 68 65 20 70 61 67 65 20 73 69 7a 65 20 63 61 The page size ca
08f0: 6e 20 62 65 20 61 6e 79 74 68 69 6e 67 20 62 65 n be anything be
0900: 74 77 65 65 6e 20 35 31 32 20 61 6e 64 20 36 35 tween 512 and 65
0910: 35 33 36 2e 0a 2a 2a 20 45 61 63 68 20 70 61 67 536..** Each pag
0920: 65 20 63 61 6e 20 62 65 20 65 69 74 68 65 72 20 e can be either
0930: 61 20 62 74 72 65 65 20 70 61 67 65 2c 20 61 20 a btree page, a
0940: 66 72 65 65 6c 69 73 74 20 70 61 67 65 20 6f 72 freelist page or
0950: 20 61 6e 20 6f 76 65 72 66 6c 6f 77 0a 2a 2a 20 an overflow.**
0960: 70 61 67 65 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 page..**.** The
0970: 66 69 72 73 74 20 70 61 67 65 20 69 73 20 61 6c first page is al
0980: 77 61 79 73 20 61 20 62 74 72 65 65 20 70 61 67 ways a btree pag
0990: 65 2e 20 20 54 68 65 20 66 69 72 73 74 20 31 30 e. The first 10
09a0: 30 20 62 79 74 65 73 20 6f 66 20 74 68 65 20 66 0 bytes of the f
09b0: 69 72 73 74 0a 2a 2a 20 70 61 67 65 20 63 6f 6e irst.** page con
09c0: 74 61 69 6e 20 61 20 73 70 65 63 69 61 6c 20 68 tain a special h
09d0: 65 61 64 65 72 20 28 74 68 65 20 22 66 69 6c 65 eader (the "file
09e0: 20 68 65 61 64 65 72 22 29 20 74 68 61 74 20 64 header") that d
09f0: 65 73 63 72 69 62 65 73 20 74 68 65 20 66 69 6c escribes the fil
0a00: 65 2e 0a 2a 2a 20 54 68 65 20 66 6f 72 6d 61 74 e..** The format
0a10: 20 6f 66 20 74 68 65 20 66 69 6c 65 20 68 65 61 of the file hea
0a20: 64 65 72 20 69 73 20 61 73 20 66 6f 6c 6c 6f 77 der is as follow
0a30: 73 3a 0a 2a 2a 0a 2a 2a 20 20 20 4f 46 46 53 45 s:.**.** OFFSE
0a40: 54 20 20 20 53 49 5a 45 20 20 20 20 44 45 53 43 T SIZE DESC
0a50: 52 49 50 54 49 4f 4e 0a 2a 2a 20 20 20 20 20 20 RIPTION.**
0a60: 30 20 20 20 20 20 20 31 36 20 20 20 20 20 48 65 0 16 He
0a70: 61 64 65 72 20 73 74 72 69 6e 67 3a 20 22 53 51 ader string: "SQ
0a80: 4c 69 74 65 20 66 6f 72 6d 61 74 20 33 5c 30 30 Lite format 3\00
0a90: 30 22 0a 2a 2a 20 20 20 20 20 31 36 20 20 20 20 0".** 16
0aa0: 20 20 20 32 20 20 20 20 20 50 61 67 65 20 73 69 2 Page si
0ab0: 7a 65 20 69 6e 20 62 79 74 65 73 2e 20 20 0a 2a ze in bytes. .*
0ac0: 2a 20 20 20 20 20 31 38 20 20 20 20 20 20 20 31 * 18 1
0ad0: 20 20 20 20 20 46 69 6c 65 20 66 6f 72 6d 61 74 File format
0ae0: 20 77 72 69 74 65 20 76 65 72 73 69 6f 6e 0a 2a write version.*
0af0: 2a 20 20 20 20 20 31 39 20 20 20 20 20 20 20 31 * 19 1
0b00: 20 20 20 20 20 46 69 6c 65 20 66 6f 72 6d 61 74 File format
0b10: 20 72 65 61 64 20 76 65 72 73 69 6f 6e 0a 2a 2a read version.**
0b20: 20 20 20 20 20 32 30 20 20 20 20 20 20 20 31 20 20 1
0b30: 20 20 20 20 42 79 74 65 73 20 6f 66 20 75 6e 75 Bytes of unu
0b40: 73 65 64 20 73 70 61 63 65 20 61 74 20 74 68 65 sed space at the
0b50: 20 65 6e 64 20 6f 66 20 65 61 63 68 20 70 61 67 end of each pag
0b60: 65 0a 2a 2a 20 20 20 20 20 32 31 20 20 20 20 20 e.** 21
0b70: 20 20 31 20 20 20 20 20 4d 61 78 20 65 6d 62 65 1 Max embe
0b80: 64 64 65 64 20 70 61 79 6c 6f 61 64 20 66 72 61 dded payload fra
0b90: 63 74 69 6f 6e 0a 2a 2a 20 20 20 20 20 32 32 20 ction.** 22
0ba0: 20 20 20 20 20 20 31 20 20 20 20 20 4d 69 6e 20 1 Min
0bb0: 65 6d 62 65 64 64 65 64 20 70 61 79 6c 6f 61 64 embedded payload
0bc0: 20 66 72 61 63 74 69 6f 6e 0a 2a 2a 20 20 20 20 fraction.**
0bd0: 20 32 33 20 20 20 20 20 20 20 31 20 20 20 20 20 23 1
0be0: 4d 69 6e 20 6c 65 61 66 20 70 61 79 6c 6f 61 64 Min leaf payload
0bf0: 20 66 72 61 63 74 69 6f 6e 0a 2a 2a 20 20 20 20 fraction.**
0c00: 20 32 34 20 20 20 20 20 20 20 34 20 20 20 20 20 24 4
0c10: 46 69 6c 65 20 63 68 61 6e 67 65 20 63 6f 75 6e File change coun
0c20: 74 65 72 0a 2a 2a 20 20 20 20 20 32 38 20 20 20 ter.** 28
0c30: 20 20 20 20 34 20 20 20 20 20 52 65 73 65 72 76 4 Reserv
0c40: 65 64 20 66 6f 72 20 66 75 74 75 72 65 20 75 73 ed for future us
0c50: 65 0a 2a 2a 20 20 20 20 20 33 32 20 20 20 20 20 e.** 32
0c60: 20 20 34 20 20 20 20 20 46 69 72 73 74 20 66 72 4 First fr
0c70: 65 65 6c 69 73 74 20 70 61 67 65 0a 2a 2a 20 20 eelist page.**
0c80: 20 20 20 33 36 20 20 20 20 20 20 20 34 20 20 20 36 4
0c90: 20 20 4e 75 6d 62 65 72 20 6f 66 20 66 72 65 65 Number of free
0ca0: 6c 69 73 74 20 70 61 67 65 73 20 69 6e 20 74 68 list pages in th
0cb0: 65 20 66 69 6c 65 0a 2a 2a 20 20 20 20 20 34 30 e file.** 40
0cc0: 20 20 20 20 20 20 36 30 20 20 20 20 20 31 35 20 60 15
0cd0: 34 2d 62 79 74 65 20 6d 65 74 61 20 76 61 6c 75 4-byte meta valu
0ce0: 65 73 20 70 61 73 73 65 64 20 74 6f 20 68 69 67 es passed to hig
0cf0: 68 65 72 20 6c 61 79 65 72 73 0a 2a 2a 0a 2a 2a her layers.**.**
0d00: 20 41 6c 6c 20 6f 66 20 74 68 65 20 69 6e 74 65 All of the inte
0d10: 67 65 72 20 76 61 6c 75 65 73 20 61 72 65 20 62 ger values are b
0d20: 69 67 2d 65 6e 64 69 61 6e 20 28 6d 6f 73 74 20 ig-endian (most
0d30: 73 69 67 6e 69 66 69 63 61 6e 74 20 62 79 74 65 significant byte
0d40: 20 66 69 72 73 74 29 2e 0a 2a 2a 0a 2a 2a 20 54 first)..**.** T
0d50: 68 65 20 66 69 6c 65 20 63 68 61 6e 67 65 20 63 he file change c
0d60: 6f 75 6e 74 65 72 20 69 73 20 69 6e 63 72 65 6d ounter is increm
0d70: 65 6e 74 65 64 20 77 68 65 6e 20 74 68 65 20 64 ented when the d
0d80: 61 74 61 62 61 73 65 20 69 73 20 63 68 61 6e 67 atabase is chang
0d90: 65 64 0a 2a 2a 20 54 68 69 73 20 63 6f 75 6e 74 ed.** This count
0da0: 65 72 20 61 6c 6c 6f 77 73 20 6f 74 68 65 72 20 er allows other
0db0: 70 72 6f 63 65 73 73 65 73 20 74 6f 20 6b 6e 6f processes to kno
0dc0: 77 20 77 68 65 6e 20 74 68 65 20 66 69 6c 65 20 w when the file
0dd0: 68 61 73 20 63 68 61 6e 67 65 64 0a 2a 2a 20 61 has changed.** a
0de0: 6e 64 20 74 68 75 73 20 77 68 65 6e 20 74 68 65 nd thus when the
0df0: 79 20 6e 65 65 64 20 74 6f 20 66 6c 75 73 68 20 y need to flush
0e00: 74 68 65 69 72 20 63 61 63 68 65 2e 0a 2a 2a 0a their cache..**.
0e10: 2a 2a 20 54 68 65 20 6d 61 78 20 65 6d 62 65 64 ** The max embed
0e20: 64 65 64 20 70 61 79 6c 6f 61 64 20 66 72 61 63 ded payload frac
0e30: 74 69 6f 6e 20 69 73 20 74 68 65 20 61 6d 6f 75 tion is the amou
0e40: 6e 74 20 6f 66 20 74 68 65 20 74 6f 74 61 6c 20 nt of the total
0e50: 75 73 61 62 6c 65 0a 2a 2a 20 73 70 61 63 65 20 usable.** space
0e60: 69 6e 20 61 20 70 61 67 65 20 74 68 61 74 20 63 in a page that c
0e70: 61 6e 20 62 65 20 63 6f 6e 73 75 6d 65 64 20 62 an be consumed b
0e80: 79 20 61 20 73 69 6e 67 6c 65 20 63 65 6c 6c 20 y a single cell
0e90: 66 6f 72 20 73 74 61 6e 64 61 72 64 0a 2a 2a 20 for standard.**
0ea0: 42 2d 74 72 65 65 20 28 6e 6f 6e 2d 4c 45 41 46 B-tree (non-LEAF
0eb0: 44 41 54 41 29 20 74 61 62 6c 65 73 2e 20 20 41 DATA) tables. A
0ec0: 20 76 61 6c 75 65 20 6f 66 20 32 35 35 20 6d 65 value of 255 me
0ed0: 61 6e 73 20 31 30 30 25 2e 20 20 54 68 65 20 64 ans 100%. The d
0ee0: 65 66 61 75 6c 74 0a 2a 2a 20 69 73 20 74 6f 20 efault.** is to
0ef0: 6c 69 6d 69 74 20 74 68 65 20 6d 61 78 69 6d 75 limit the maximu
0f00: 6d 20 63 65 6c 6c 20 73 69 7a 65 20 73 6f 20 74 m cell size so t
0f10: 68 61 74 20 61 74 20 6c 65 61 73 74 20 34 20 63 hat at least 4 c
0f20: 65 6c 6c 73 20 77 69 6c 6c 20 66 69 74 0a 2a 2a ells will fit.**
0f30: 20 6f 6e 20 6f 6e 65 20 70 61 67 65 2e 20 20 54 on one page. T
0f40: 68 75 73 20 74 68 65 20 64 65 66 61 75 6c 74 20 hus the default
0f50: 6d 61 78 20 65 6d 62 65 64 64 65 64 20 70 61 79 max embedded pay
0f60: 6c 6f 61 64 20 66 72 61 63 74 69 6f 6e 20 69 73 load fraction is
0f70: 20 36 34 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 74 68 64..**.** If th
0f80: 65 20 70 61 79 6c 6f 61 64 20 66 6f 72 20 61 20 e payload for a
0f90: 63 65 6c 6c 20 69 73 20 6c 61 72 67 65 72 20 74 cell is larger t
0fa0: 68 61 6e 20 74 68 65 20 6d 61 78 20 70 61 79 6c han the max payl
0fb0: 6f 61 64 2c 20 74 68 65 6e 20 65 78 74 72 61 0a oad, then extra.
0fc0: 2a 2a 20 70 61 79 6c 6f 61 64 20 69 73 20 73 70 ** payload is sp
0fd0: 69 6c 6c 65 64 20 74 6f 20 6f 76 65 72 66 6c 6f illed to overflo
0fe0: 77 20 70 61 67 65 73 2e 20 20 4f 6e 63 65 20 61 w pages. Once a
0ff0: 6e 20 6f 76 65 72 66 6c 6f 77 20 70 61 67 65 20 n overflow page
1000: 69 73 20 61 6c 6c 6f 63 61 74 65 64 2c 0a 2a 2a is allocated,.**
1010: 20 61 73 20 6d 61 6e 79 20 62 79 74 65 73 20 61 as many bytes a
1020: 73 20 70 6f 73 73 69 62 6c 65 20 61 72 65 20 6d s possible are m
1030: 6f 76 65 64 20 69 6e 74 6f 20 74 68 65 20 6f 76 oved into the ov
1040: 65 72 66 6c 6f 77 20 70 61 67 65 73 20 77 69 74 erflow pages wit
1050: 68 6f 75 74 20 6c 65 74 74 69 6e 67 0a 2a 2a 20 hout letting.**
1060: 74 68 65 20 63 65 6c 6c 20 73 69 7a 65 20 64 72 the cell size dr
1070: 6f 70 20 62 65 6c 6f 77 20 74 68 65 20 6d 69 6e op below the min
1080: 20 65 6d 62 65 64 64 65 64 20 70 61 79 6c 6f 61 embedded payloa
1090: 64 20 66 72 61 63 74 69 6f 6e 2e 0a 2a 2a 0a 2a d fraction..**.*
10a0: 2a 20 54 68 65 20 6d 69 6e 20 6c 65 61 66 20 70 * The min leaf p
10b0: 61 79 6c 6f 61 64 20 66 72 61 63 74 69 6f 6e 20 ayload fraction
10c0: 69 73 20 6c 69 6b 65 20 74 68 65 20 6d 69 6e 20 is like the min
10d0: 65 6d 62 65 64 64 65 64 20 70 61 79 6c 6f 61 64 embedded payload
10e0: 20 66 72 61 63 74 69 6f 6e 0a 2a 2a 20 65 78 63 fraction.** exc
10f0: 65 70 74 20 74 68 61 74 20 69 74 20 61 70 70 6c ept that it appl
1100: 69 65 73 20 74 6f 20 6c 65 61 66 20 6e 6f 64 65 ies to leaf node
1110: 73 20 69 6e 20 61 20 4c 45 41 46 44 41 54 41 20 s in a LEAFDATA
1120: 74 72 65 65 2e 20 20 54 68 65 20 6d 61 78 69 6d tree. The maxim
1130: 75 6d 0a 2a 2a 20 70 61 79 6c 6f 61 64 20 66 72 um.** payload fr
1140: 61 63 74 69 6f 6e 20 66 6f 72 20 61 20 4c 45 41 action for a LEA
1150: 46 44 41 54 41 20 74 72 65 65 20 69 73 20 61 6c FDATA tree is al
1160: 77 61 79 73 20 31 30 30 25 20 28 6f 72 20 32 35 ways 100% (or 25
1170: 35 29 20 61 6e 64 20 69 74 0a 2a 2a 20 6e 6f 74 5) and it.** not
1180: 20 73 70 65 63 69 66 69 65 64 20 69 6e 20 74 68 specified in th
1190: 65 20 68 65 61 64 65 72 2e 0a 2a 2a 0a 2a 2a 20 e header..**.**
11a0: 45 61 63 68 20 62 74 72 65 65 20 70 61 67 65 73 Each btree pages
11b0: 20 69 73 20 64 69 76 69 64 65 64 20 69 6e 74 6f is divided into
11c0: 20 74 68 72 65 65 20 73 65 63 74 69 6f 6e 73 3a three sections:
11d0: 20 20 54 68 65 20 68 65 61 64 65 72 2c 20 74 68 The header, th
11e0: 65 0a 2a 2a 20 63 65 6c 6c 20 70 6f 69 6e 74 65 e.** cell pointe
11f0: 72 20 61 72 72 61 79 2c 20 61 6e 64 20 74 68 65 r array, and the
1200: 20 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 20 61 72 cell content ar
1210: 65 61 2e 20 20 50 61 67 65 20 31 20 61 6c 73 6f ea. Page 1 also
1220: 20 68 61 73 20 61 20 31 30 30 2d 62 79 74 65 0a has a 100-byte.
1230: 2a 2a 20 66 69 6c 65 20 68 65 61 64 65 72 20 74 ** file header t
1240: 68 61 74 20 6f 63 63 75 72 73 20 62 65 66 6f 72 hat occurs befor
1250: 65 20 74 68 65 20 70 61 67 65 20 68 65 61 64 65 e the page heade
1260: 72 2e 0a 2a 2a 0a 2a 2a 20 20 20 20 20 20 7c 2d r..**.** |-
1270: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 7c ---------------|
1280: 0a 2a 2a 20 20 20 20 20 20 7c 20 66 69 6c 65 20 .** | file
1290: 68 65 61 64 65 72 20 20 20 20 7c 20 20 20 31 30 header | 10
12a0: 30 20 62 79 74 65 73 2e 20 20 50 61 67 65 20 31 0 bytes. Page 1
12b0: 20 6f 6e 6c 79 2e 0a 2a 2a 20 20 20 20 20 20 7c only..** |
12c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
12d0: 7c 0a 2a 2a 20 20 20 20 20 20 7c 20 70 61 67 65 |.** | page
12e0: 20 68 65 61 64 65 72 20 20 20 20 7c 20 20 20 38 header | 8
12f0: 20 62 79 74 65 73 20 66 6f 72 20 6c 65 61 76 65 bytes for leave
1300: 73 2e 20 20 31 32 20 62 79 74 65 73 20 66 6f 72 s. 12 bytes for
1310: 20 69 6e 74 65 72 69 6f 72 20 6e 6f 64 65 73 0a interior nodes.
1320: 2a 2a 20 20 20 20 20 20 7c 2d 2d 2d 2d 2d 2d 2d ** |-------
1330: 2d 2d 2d 2d 2d 2d 2d 2d 2d 7c 0a 2a 2a 20 20 20 ---------|.**
1340: 20 20 20 7c 20 63 65 6c 6c 20 70 6f 69 6e 74 65 | cell pointe
1350: 72 20 20 20 7c 20 20 20 7c 20 20 32 20 62 79 74 r | | 2 byt
1360: 65 73 20 70 65 72 20 63 65 6c 6c 2e 20 20 53 6f es per cell. So
1370: 72 74 65 64 20 6f 72 64 65 72 2e 0a 2a 2a 20 20 rted order..**
1380: 20 20 20 20 7c 20 61 72 72 61 79 20 20 20 20 20 | array
1390: 20 20 20 20 20 7c 20 20 20 7c 20 20 47 72 6f 77 | | Grow
13a0: 73 20 64 6f 77 6e 77 61 72 64 0a 2a 2a 20 20 20 s downward.**
13b0: 20 20 20 7c 20 20 20 20 20 20 20 20 20 20 20 20 |
13c0: 20 20 20 20 7c 20 20 20 76 0a 2a 2a 20 20 20 20 | v.**
13d0: 20 20 7c 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d |-------------
13e0: 2d 2d 2d 7c 0a 2a 2a 20 20 20 20 20 20 7c 20 75 ---|.** | u
13f0: 6e 61 6c 6c 6f 63 61 74 65 64 20 20 20 20 7c 0a nallocated |.
1400: 2a 2a 20 20 20 20 20 20 7c 20 73 70 61 63 65 20 ** | space
1410: 20 20 20 20 20 20 20 20 20 7c 0a 2a 2a 20 20 20 |.**
1420: 20 20 20 7c 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d |------------
1430: 2d 2d 2d 2d 7c 20 20 20 5e 20 20 47 72 6f 77 73 ----| ^ Grows
1440: 20 75 70 77 61 72 64 73 0a 2a 2a 20 20 20 20 20 upwards.**
1450: 20 7c 20 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 20 | cell content
1460: 20 20 7c 20 20 20 7c 20 20 41 72 62 69 74 72 61 | | Arbitra
1470: 72 79 20 6f 72 64 65 72 20 69 6e 74 65 72 73 70 ry order intersp
1480: 65 72 73 65 64 20 77 69 74 68 20 66 72 65 65 62 ersed with freeb
1490: 6c 6f 63 6b 73 2e 0a 2a 2a 20 20 20 20 20 20 7c locks..** |
14a0: 20 61 72 65 61 20 20 20 20 20 20 20 20 20 20 20 area
14b0: 7c 20 20 20 7c 20 20 61 6e 64 20 66 72 65 65 20 | | and free
14c0: 73 70 61 63 65 20 66 72 61 67 6d 65 6e 74 73 2e space fragments.
14d0: 0a 2a 2a 20 20 20 20 20 20 7c 2d 2d 2d 2d 2d 2d .** |------
14e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 7c 0a 2a 2a 0a 2a ----------|.**.*
14f0: 2a 20 54 68 65 20 70 61 67 65 20 68 65 61 64 65 * The page heade
1500: 72 73 20 6c 6f 6f 6b 73 20 6c 69 6b 65 20 74 68 rs looks like th
1510: 69 73 3a 0a 2a 2a 0a 2a 2a 20 20 20 4f 46 46 53 is:.**.** OFFS
1520: 45 54 20 20 20 53 49 5a 45 20 20 20 20 20 44 45 ET SIZE DE
1530: 53 43 52 49 50 54 49 4f 4e 0a 2a 2a 20 20 20 20 SCRIPTION.**
1540: 20 20 30 20 20 20 20 20 20 20 31 20 20 20 20 20 0 1
1550: 20 46 6c 61 67 73 2e 20 31 3a 20 69 6e 74 6b 65 Flags. 1: intke
1560: 79 2c 20 32 3a 20 7a 65 72 6f 64 61 74 61 2c 20 y, 2: zerodata,
1570: 34 3a 20 6c 65 61 66 64 61 74 61 2c 20 38 3a 20 4: leafdata, 8:
1580: 6c 65 61 66 0a 2a 2a 20 20 20 20 20 20 31 20 20 leaf.** 1
1590: 20 20 20 20 20 32 20 20 20 20 20 20 62 79 74 65 2 byte
15a0: 20 6f 66 66 73 65 74 20 74 6f 20 74 68 65 20 66 offset to the f
15b0: 69 72 73 74 20 66 72 65 65 62 6c 6f 63 6b 0a 2a irst freeblock.*
15c0: 2a 20 20 20 20 20 20 33 20 20 20 20 20 20 20 32 * 3 2
15d0: 20 20 20 20 20 20 6e 75 6d 62 65 72 20 6f 66 20 number of
15e0: 63 65 6c 6c 73 20 6f 6e 20 74 68 69 73 20 70 61 cells on this pa
15f0: 67 65 0a 2a 2a 20 20 20 20 20 20 35 20 20 20 20 ge.** 5
1600: 20 20 20 32 20 20 20 20 20 20 66 69 72 73 74 20 2 first
1610: 62 79 74 65 20 6f 66 20 74 68 65 20 63 65 6c 6c byte of the cell
1620: 20 63 6f 6e 74 65 6e 74 20 61 72 65 61 0a 2a 2a content area.**
1630: 20 20 20 20 20 20 37 20 20 20 20 20 20 20 31 20 7 1
1640: 20 20 20 20 20 6e 75 6d 62 65 72 20 6f 66 20 66 number of f
1650: 72 61 67 6d 65 6e 74 65 64 20 66 72 65 65 20 62 ragmented free b
1660: 79 74 65 73 0a 2a 2a 20 20 20 20 20 20 38 20 20 ytes.** 8
1670: 20 20 20 20 20 34 20 20 20 20 20 20 52 69 67 68 4 Righ
1680: 74 20 63 68 69 6c 64 20 28 74 68 65 20 50 74 72 t child (the Ptr
1690: 28 4e 29 20 76 61 6c 75 65 29 2e 20 20 4f 6d 69 (N) value). Omi
16a0: 74 74 65 64 20 6f 6e 20 6c 65 61 76 65 73 2e 0a tted on leaves..
16b0: 2a 2a 0a 2a 2a 20 54 68 65 20 66 6c 61 67 73 20 **.** The flags
16c0: 64 65 66 69 6e 65 20 74 68 65 20 66 6f 72 6d 61 define the forma
16d0: 74 20 6f 66 20 74 68 69 73 20 62 74 72 65 65 20 t of this btree
16e0: 70 61 67 65 2e 20 20 54 68 65 20 6c 65 61 66 20 page. The leaf
16f0: 66 6c 61 67 20 6d 65 61 6e 73 20 74 68 61 74 0a flag means that.
1700: 2a 2a 20 74 68 69 73 20 70 61 67 65 20 68 61 73 ** this page has
1710: 20 6e 6f 20 63 68 69 6c 64 72 65 6e 2e 20 20 54 no children. T
1720: 68 65 20 7a 65 72 6f 64 61 74 61 20 66 6c 61 67 he zerodata flag
1730: 20 6d 65 61 6e 73 20 74 68 61 74 20 74 68 69 73 means that this
1740: 20 70 61 67 65 20 63 61 72 72 69 65 73 0a 2a 2a page carries.**
1750: 20 6f 6e 6c 79 20 6b 65 79 73 20 61 6e 64 20 6e only keys and n
1760: 6f 20 64 61 74 61 2e 20 20 54 68 65 20 69 6e 74 o data. The int
1770: 6b 65 79 20 66 6c 61 67 20 6d 65 61 6e 73 20 74 key flag means t
1780: 68 61 74 20 74 68 65 20 6b 65 79 20 69 73 20 61 hat the key is a
1790: 20 69 6e 74 65 67 65 72 0a 2a 2a 20 77 68 69 63 integer.** whic
17a0: 68 20 69 73 20 73 74 6f 72 65 64 20 69 6e 20 74 h is stored in t
17b0: 68 65 20 6b 65 79 20 73 69 7a 65 20 65 6e 74 72 he key size entr
17c0: 79 20 6f 66 20 74 68 65 20 63 65 6c 6c 20 68 65 y of the cell he
17d0: 61 64 65 72 20 72 61 74 68 65 72 20 74 68 61 6e ader rather than
17e0: 20 69 6e 0a 2a 2a 20 74 68 65 20 70 61 79 6c 6f in.** the paylo
17f0: 61 64 20 61 72 65 61 2e 0a 2a 2a 0a 2a 2a 20 54 ad area..**.** T
1800: 68 65 20 63 65 6c 6c 20 70 6f 69 6e 74 65 72 20 he cell pointer
1810: 61 72 72 61 79 20 62 65 67 69 6e 73 20 6f 6e 20 array begins on
1820: 74 68 65 20 66 69 72 73 74 20 62 79 74 65 20 61 the first byte a
1830: 66 74 65 72 20 74 68 65 20 70 61 67 65 20 68 65 fter the page he
1840: 61 64 65 72 2e 0a 2a 2a 20 54 68 65 20 63 65 6c ader..** The cel
1850: 6c 20 70 6f 69 6e 74 65 72 20 61 72 72 61 79 20 l pointer array
1860: 63 6f 6e 74 61 69 6e 73 20 7a 65 72 6f 20 6f 72 contains zero or
1870: 20 6d 6f 72 65 20 32 2d 62 79 74 65 20 6e 75 6d more 2-byte num
1880: 62 65 72 73 20 77 68 69 63 68 20 61 72 65 0a 2a bers which are.*
1890: 2a 20 6f 66 66 73 65 74 73 20 66 72 6f 6d 20 74 * offsets from t
18a0: 68 65 20 62 65 67 69 6e 6e 69 6e 67 20 6f 66 20 he beginning of
18b0: 74 68 65 20 70 61 67 65 20 74 6f 20 74 68 65 20 the page to the
18c0: 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 20 69 6e 20 cell content in
18d0: 74 68 65 20 63 65 6c 6c 0a 2a 2a 20 63 6f 6e 74 the cell.** cont
18e0: 65 6e 74 20 61 72 65 61 2e 20 20 54 68 65 20 63 ent area. The c
18f0: 65 6c 6c 20 70 6f 69 6e 74 65 72 73 20 6f 63 63 ell pointers occ
1900: 75 72 20 69 6e 20 73 6f 72 74 65 64 20 6f 72 64 ur in sorted ord
1910: 65 72 2e 20 20 54 68 65 20 73 79 73 74 65 6d 20 er. The system
1920: 73 74 72 69 76 65 73 0a 2a 2a 20 74 6f 20 6b 65 strives.** to ke
1930: 65 70 20 66 72 65 65 20 73 70 61 63 65 20 61 66 ep free space af
1940: 74 65 72 20 74 68 65 20 6c 61 73 74 20 63 65 6c ter the last cel
1950: 6c 20 70 6f 69 6e 74 65 72 20 73 6f 20 74 68 61 l pointer so tha
1960: 74 20 6e 65 77 20 63 65 6c 6c 73 20 63 61 6e 0a t new cells can.
1970: 2a 2a 20 62 65 20 65 61 73 69 6c 79 20 61 64 64 ** be easily add
1980: 65 64 20 77 69 74 68 6f 75 74 20 68 61 76 69 6e ed without havin
1990: 67 20 74 6f 20 64 65 66 72 61 67 6d 65 6e 74 20 g to defragment
19a0: 74 68 65 20 70 61 67 65 2e 0a 2a 2a 0a 2a 2a 20 the page..**.**
19b0: 43 65 6c 6c 20 63 6f 6e 74 65 6e 74 20 69 73 20 Cell content is
19c0: 73 74 6f 72 65 64 20 61 74 20 74 68 65 20 76 65 stored at the ve
19d0: 72 79 20 65 6e 64 20 6f 66 20 74 68 65 20 70 61 ry end of the pa
19e0: 67 65 20 61 6e 64 20 67 72 6f 77 73 20 74 6f 77 ge and grows tow
19f0: 61 72 64 20 74 68 65 0a 2a 2a 20 62 65 67 69 6e ard the.** begin
1a00: 6e 69 6e 67 20 6f 66 20 74 68 65 20 70 61 67 65 ning of the page
1a10: 2e 0a 2a 2a 0a 2a 2a 20 55 6e 75 73 65 64 20 73 ..**.** Unused s
1a20: 70 61 63 65 20 77 69 74 68 69 6e 20 74 68 65 20 pace within the
1a30: 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 20 61 72 65 cell content are
1a40: 61 20 69 73 20 63 6f 6c 6c 65 63 74 65 64 20 69 a is collected i
1a50: 6e 74 6f 20 61 20 6c 69 6e 6b 65 64 20 6c 69 73 nto a linked lis
1a60: 74 20 6f 66 0a 2a 2a 20 66 72 65 65 62 6c 6f 63 t of.** freebloc
1a70: 6b 73 2e 20 20 45 61 63 68 20 66 72 65 65 62 6c ks. Each freebl
1a80: 6f 63 6b 20 69 73 20 61 74 20 6c 65 61 73 74 20 ock is at least
1a90: 34 20 62 79 74 65 73 20 69 6e 20 73 69 7a 65 2e 4 bytes in size.
1aa0: 20 20 54 68 65 20 62 79 74 65 20 6f 66 66 73 65 The byte offse
1ab0: 74 0a 2a 2a 20 74 6f 20 74 68 65 20 66 69 72 73 t.** to the firs
1ac0: 74 20 66 72 65 65 62 6c 6f 63 6b 20 69 73 20 67 t freeblock is g
1ad0: 69 76 65 6e 20 69 6e 20 74 68 65 20 68 65 61 64 iven in the head
1ae0: 65 72 2e 20 20 46 72 65 65 62 6c 6f 63 6b 73 20 er. Freeblocks
1af0: 6f 63 63 75 72 20 69 6e 0a 2a 2a 20 69 6e 63 72 occur in.** incr
1b00: 65 61 73 69 6e 67 20 6f 72 64 65 72 2e 20 20 42 easing order. B
1b10: 65 63 61 75 73 65 20 61 20 66 72 65 65 62 6c 6f ecause a freeblo
1b20: 63 6b 20 6d 75 73 74 20 62 65 20 61 74 20 6c 65 ck must be at le
1b30: 61 73 74 20 34 20 62 79 74 65 73 20 69 6e 20 73 ast 4 bytes in s
1b40: 69 7a 65 2c 0a 2a 2a 20 61 6e 79 20 67 72 6f 75 ize,.** any grou
1b50: 70 20 6f 66 20 33 20 6f 72 20 66 65 77 65 72 20 p of 3 or fewer
1b60: 75 6e 75 73 65 64 20 62 79 74 65 73 20 69 6e 20 unused bytes in
1b70: 74 68 65 20 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 the cell content
1b80: 20 61 72 65 61 20 63 61 6e 6e 6f 74 0a 2a 2a 20 area cannot.**
1b90: 65 78 69 73 74 20 6f 6e 20 74 68 65 20 66 72 65 exist on the fre
1ba0: 65 62 6c 6f 63 6b 20 63 68 61 69 6e 2e 20 20 41 eblock chain. A
1bb0: 20 67 72 6f 75 70 20 6f 66 20 33 20 6f 72 20 66 group of 3 or f
1bc0: 65 77 65 72 20 66 72 65 65 20 62 79 74 65 73 20 ewer free bytes
1bd0: 69 73 20 63 61 6c 6c 65 64 0a 2a 2a 20 61 20 66 is called.** a f
1be0: 72 61 67 6d 65 6e 74 2e 20 20 54 68 65 20 74 6f ragment. The to
1bf0: 74 61 6c 20 6e 75 6d 62 65 72 20 6f 66 20 62 79 tal number of by
1c00: 74 65 73 20 69 6e 20 61 6c 6c 20 66 72 61 67 6d tes in all fragm
1c10: 65 6e 74 73 20 69 73 20 72 65 63 6f 72 64 65 64 ents is recorded
1c20: 2e 0a 2a 2a 20 69 6e 20 74 68 65 20 70 61 67 65 ..** in the page
1c30: 20 68 65 61 64 65 72 20 61 74 20 6f 66 66 73 65 header at offse
1c40: 74 20 37 2e 0a 2a 2a 0a 2a 2a 20 20 20 20 53 49 t 7..**.** SI
1c50: 5a 45 20 20 20 20 44 45 53 43 52 49 50 54 49 4f ZE DESCRIPTIO
1c60: 4e 0a 2a 2a 20 20 20 20 20 20 32 20 20 20 20 20 N.** 2
1c70: 42 79 74 65 20 6f 66 66 73 65 74 20 6f 66 20 74 Byte offset of t
1c80: 68 65 20 6e 65 78 74 20 66 72 65 65 62 6c 6f 63 he next freebloc
1c90: 6b 0a 2a 2a 20 20 20 20 20 20 32 20 20 20 20 20 k.** 2
1ca0: 42 79 74 65 73 20 69 6e 20 74 68 69 73 20 66 72 Bytes in this fr
1cb0: 65 65 62 6c 6f 63 6b 0a 2a 2a 0a 2a 2a 20 43 65 eeblock.**.** Ce
1cc0: 6c 6c 73 20 61 72 65 20 6f 66 20 76 61 72 69 61 lls are of varia
1cd0: 62 6c 65 20 6c 65 6e 67 74 68 2e 20 20 43 65 6c ble length. Cel
1ce0: 6c 73 20 61 72 65 20 73 74 6f 72 65 64 20 69 6e ls are stored in
1cf0: 20 74 68 65 20 63 65 6c 6c 20 63 6f 6e 74 65 6e the cell conten
1d00: 74 20 61 72 65 61 20 61 74 0a 2a 2a 20 74 68 65 t area at.** the
1d10: 20 65 6e 64 20 6f 66 20 74 68 65 20 70 61 67 65 end of the page
1d20: 2e 20 20 50 6f 69 6e 74 65 72 73 20 74 6f 20 74 . Pointers to t
1d30: 68 65 20 63 65 6c 6c 73 20 61 72 65 20 69 6e 20 he cells are in
1d40: 74 68 65 20 63 65 6c 6c 20 70 6f 69 6e 74 65 72 the cell pointer
1d50: 20 61 72 72 61 79 0a 2a 2a 20 74 68 61 74 20 69 array.** that i
1d60: 6d 6d 65 64 69 61 74 65 6c 79 20 66 6f 6c 6c 6f mmediately follo
1d70: 77 73 20 74 68 65 20 70 61 67 65 20 68 65 61 64 ws the page head
1d80: 65 72 2e 20 20 43 65 6c 6c 73 20 69 73 20 6e 6f er. Cells is no
1d90: 74 20 6e 65 63 65 73 73 61 72 69 6c 79 0a 2a 2a t necessarily.**
1da0: 20 63 6f 6e 74 69 67 75 6f 75 73 20 6f 72 20 69 contiguous or i
1db0: 6e 20 6f 72 64 65 72 2c 20 62 75 74 20 63 65 6c n order, but cel
1dc0: 6c 20 70 6f 69 6e 74 65 72 73 20 61 72 65 20 63 l pointers are c
1dd0: 6f 6e 74 69 67 75 6f 75 73 20 61 6e 64 20 69 6e ontiguous and in
1de0: 20 6f 72 64 65 72 2e 0a 2a 2a 0a 2a 2a 20 43 65 order..**.** Ce
1df0: 6c 6c 20 63 6f 6e 74 65 6e 74 20 6d 61 6b 65 73 ll content makes
1e00: 20 75 73 65 20 6f 66 20 76 61 72 69 61 62 6c 65 use of variable
1e10: 20 6c 65 6e 67 74 68 20 69 6e 74 65 67 65 72 73 length integers
1e20: 2e 20 20 41 20 76 61 72 69 61 62 6c 65 0a 2a 2a . A variable.**
1e30: 20 6c 65 6e 67 74 68 20 69 6e 74 65 67 65 72 20 length integer
1e40: 69 73 20 31 20 74 6f 20 39 20 62 79 74 65 73 20 is 1 to 9 bytes
1e50: 77 68 65 72 65 20 74 68 65 20 6c 6f 77 65 72 20 where the lower
1e60: 37 20 62 69 74 73 20 6f 66 20 65 61 63 68 20 0a 7 bits of each .
1e70: 2a 2a 20 62 79 74 65 20 61 72 65 20 75 73 65 64 ** byte are used
1e80: 2e 20 20 54 68 65 20 69 6e 74 65 67 65 72 20 63 . The integer c
1e90: 6f 6e 73 69 73 74 73 20 6f 66 20 61 6c 6c 20 62 onsists of all b
1ea0: 79 74 65 73 20 74 68 61 74 20 68 61 76 65 20 62 ytes that have b
1eb0: 69 74 20 38 20 73 65 74 20 61 6e 64 0a 2a 2a 20 it 8 set and.**
1ec0: 74 68 65 20 66 69 72 73 74 20 62 79 74 65 20 77 the first byte w
1ed0: 69 74 68 20 62 69 74 20 38 20 63 6c 65 61 72 2e ith bit 8 clear.
1ee0: 20 20 54 68 65 20 6d 6f 73 74 20 73 69 67 6e 69 The most signi
1ef0: 66 69 63 61 6e 74 20 62 79 74 65 20 6f 66 20 74 ficant byte of t
1f00: 68 65 20 69 6e 74 65 67 65 72 0a 2a 2a 20 61 70 he integer.** ap
1f10: 70 65 61 72 73 20 66 69 72 73 74 2e 20 20 41 20 pears first. A
1f20: 76 61 72 69 61 62 6c 65 2d 6c 65 6e 67 74 68 20 variable-length
1f30: 69 6e 74 65 67 65 72 20 6d 61 79 20 6e 6f 74 20 integer may not
1f40: 62 65 20 6d 6f 72 65 20 74 68 61 6e 20 39 20 62 be more than 9 b
1f50: 79 74 65 73 20 6c 6f 6e 67 2e 0a 2a 2a 20 41 73 ytes long..** As
1f60: 20 61 20 73 70 65 63 69 61 6c 20 63 61 73 65 2c a special case,
1f70: 20 61 6c 6c 20 38 20 62 79 74 65 73 20 6f 66 20 all 8 bytes of
1f80: 74 68 65 20 39 74 68 20 62 79 74 65 20 61 72 65 the 9th byte are
1f90: 20 75 73 65 64 20 61 73 20 64 61 74 61 2e 20 20 used as data.
1fa0: 54 68 69 73 0a 2a 2a 20 61 6c 6c 6f 77 73 20 61 This.** allows a
1fb0: 20 36 34 2d 62 69 74 20 69 6e 74 65 67 65 72 20 64-bit integer
1fc0: 74 6f 20 62 65 20 65 6e 63 6f 64 65 64 20 69 6e to be encoded in
1fd0: 20 39 20 62 79 74 65 73 2e 0a 2a 2a 0a 2a 2a 20 9 bytes..**.**
1fe0: 20 20 20 30 78 30 30 20 20 20 20 20 20 20 20 20 0x00
1ff0: 20 20 20 20 20 20 20 20 20 20 20 20 20 62 65 63 bec
2000: 6f 6d 65 73 20 20 30 78 30 30 30 30 30 30 30 30 omes 0x00000000
2010: 0a 2a 2a 20 20 20 20 30 78 37 66 20 20 20 20 20 .** 0x7f
2020: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
2030: 20 62 65 63 6f 6d 65 73 20 20 30 78 30 30 30 30 becomes 0x0000
2040: 30 30 37 66 0a 2a 2a 20 20 20 20 30 78 38 31 20 007f.** 0x81
2050: 30 78 30 30 20 20 20 20 20 20 20 20 20 20 20 20 0x00
2060: 20 20 20 20 20 62 65 63 6f 6d 65 73 20 20 30 78 becomes 0x
2070: 30 30 30 30 30 30 38 30 0a 2a 2a 20 20 20 20 30 00000080.** 0
2080: 78 38 32 20 30 78 30 30 20 20 20 20 20 20 20 20 x82 0x00
2090: 20 20 20 20 20 20 20 20 20 62 65 63 6f 6d 65 73 becomes
20a0: 20 20 30 78 30 30 30 30 30 31 30 30 0a 2a 2a 20 0x00000100.**
20b0: 20 20 20 30 78 38 30 20 30 78 37 66 20 20 20 20 0x80 0x7f
20c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 62 65 63 bec
20d0: 6f 6d 65 73 20 20 30 78 30 30 30 30 30 30 37 66 omes 0x0000007f
20e0: 0a 2a 2a 20 20 20 20 30 78 38 61 20 30 78 39 31 .** 0x8a 0x91
20f0: 20 30 78 64 31 20 30 78 61 63 20 30 78 37 38 20 0xd1 0xac 0x78
2100: 20 62 65 63 6f 6d 65 73 20 20 30 78 31 32 33 34 becomes 0x1234
2110: 35 36 37 38 0a 2a 2a 20 20 20 20 30 78 38 31 20 5678.** 0x81
2120: 30 78 38 31 20 30 78 38 31 20 30 78 38 31 20 30 0x81 0x81 0x81 0
2130: 78 30 31 20 20 62 65 63 6f 6d 65 73 20 20 30 78 x01 becomes 0x
2140: 31 30 32 30 34 30 38 31 0a 2a 2a 0a 2a 2a 20 56 10204081.**.** V
2150: 61 72 69 61 62 6c 65 20 6c 65 6e 67 74 68 20 69 ariable length i
2160: 6e 74 65 67 65 72 73 20 61 72 65 20 75 73 65 64 ntegers are used
2170: 20 66 6f 72 20 72 6f 77 69 64 73 20 61 6e 64 20 for rowids and
2180: 74 6f 20 68 6f 6c 64 20 74 68 65 20 6e 75 6d 62 to hold the numb
2190: 65 72 20 6f 66 0a 2a 2a 20 62 79 74 65 73 20 6f er of.** bytes o
21a0: 66 20 6b 65 79 20 61 6e 64 20 64 61 74 61 20 69 f key and data i
21b0: 6e 20 61 20 62 74 72 65 65 20 63 65 6c 6c 2e 0a n a btree cell..
21c0: 2a 2a 0a 2a 2a 20 54 68 65 20 63 6f 6e 74 65 6e **.** The conten
21d0: 74 20 6f 66 20 61 20 63 65 6c 6c 20 6c 6f 6f 6b t of a cell look
21e0: 73 20 6c 69 6b 65 20 74 68 69 73 3a 0a 2a 2a 0a s like this:.**.
21f0: 2a 2a 20 20 20 20 53 49 5a 45 20 20 20 20 44 45 ** SIZE DE
2200: 53 43 52 49 50 54 49 4f 4e 0a 2a 2a 20 20 20 20 SCRIPTION.**
2210: 20 20 34 20 20 20 20 20 50 61 67 65 20 6e 75 6d 4 Page num
2220: 62 65 72 20 6f 66 20 74 68 65 20 6c 65 66 74 20 ber of the left
2230: 63 68 69 6c 64 2e 20 4f 6d 69 74 74 65 64 20 69 child. Omitted i
2240: 66 20 6c 65 61 66 20 66 6c 61 67 20 69 73 20 73 f leaf flag is s
2250: 65 74 2e 0a 2a 2a 20 20 20 20 20 76 61 72 20 20 et..** var
2260: 20 20 4e 75 6d 62 65 72 20 6f 66 20 62 79 74 65 Number of byte
2270: 73 20 6f 66 20 64 61 74 61 2e 20 4f 6d 69 74 74 s of data. Omitt
2280: 65 64 20 69 66 20 74 68 65 20 7a 65 72 6f 64 61 ed if the zeroda
2290: 74 61 20 66 6c 61 67 20 69 73 20 73 65 74 2e 0a ta flag is set..
22a0: 2a 2a 20 20 20 20 20 76 61 72 20 20 20 20 4e 75 ** var Nu
22b0: 6d 62 65 72 20 6f 66 20 62 79 74 65 73 20 6f 66 mber of bytes of
22c0: 20 6b 65 79 2e 20 4f 72 20 74 68 65 20 6b 65 79 key. Or the key
22d0: 20 69 74 73 65 6c 66 20 69 66 20 69 6e 74 6b 65 itself if intke
22e0: 79 20 66 6c 61 67 20 69 73 20 73 65 74 2e 0a 2a y flag is set..*
22f0: 2a 20 20 20 20 20 20 2a 20 20 20 20 20 50 61 79 * * Pay
2300: 6c 6f 61 64 0a 2a 2a 20 20 20 20 20 20 34 20 20 load.** 4
2310: 20 20 20 46 69 72 73 74 20 70 61 67 65 20 6f 66 First page of
2320: 20 74 68 65 20 6f 76 65 72 66 6c 6f 77 20 63 68 the overflow ch
2330: 61 69 6e 2e 20 20 4f 6d 69 74 74 65 64 20 69 66 ain. Omitted if
2340: 20 6e 6f 20 6f 76 65 72 66 6c 6f 77 0a 2a 2a 0a no overflow.**.
2350: 2a 2a 20 4f 76 65 72 66 6c 6f 77 20 70 61 67 65 ** Overflow page
2360: 73 20 66 6f 72 6d 20 61 20 6c 69 6e 6b 65 64 20 s form a linked
2370: 6c 69 73 74 2e 20 20 45 61 63 68 20 70 61 67 65 list. Each page
2380: 20 65 78 63 65 70 74 20 74 68 65 20 6c 61 73 74 except the last
2390: 20 69 73 20 63 6f 6d 70 6c 65 74 65 6c 79 0a 2a is completely.*
23a0: 2a 20 66 69 6c 6c 65 64 20 77 69 74 68 20 64 61 * filled with da
23b0: 74 61 20 28 70 61 67 65 73 69 7a 65 20 2d 20 34 ta (pagesize - 4
23c0: 20 62 79 74 65 73 29 2e 20 20 54 68 65 20 6c 61 bytes). The la
23d0: 73 74 20 70 61 67 65 20 63 61 6e 20 68 61 76 65 st page can have
23e0: 20 61 73 20 6c 69 74 74 6c 65 0a 2a 2a 20 61 73 as little.** as
23f0: 20 31 20 62 79 74 65 20 6f 66 20 64 61 74 61 2e 1 byte of data.
2400: 0a 2a 2a 0a 2a 2a 20 20 20 20 53 49 5a 45 20 20 .**.** SIZE
2410: 20 20 44 45 53 43 52 49 50 54 49 4f 4e 0a 2a 2a DESCRIPTION.**
2420: 20 20 20 20 20 20 34 20 20 20 20 20 50 61 67 65 4 Page
2430: 20 6e 75 6d 62 65 72 20 6f 66 20 6e 65 78 74 20 number of next
2440: 6f 76 65 72 66 6c 6f 77 20 70 61 67 65 0a 2a 2a overflow page.**
2450: 20 20 20 20 20 20 2a 20 20 20 20 20 44 61 74 61 * Data
2460: 0a 2a 2a 0a 2a 2a 20 46 72 65 65 6c 69 73 74 20 .**.** Freelist
2470: 70 61 67 65 73 20 63 6f 6d 65 20 69 6e 20 74 77 pages come in tw
2480: 6f 20 73 75 62 74 79 70 65 73 3a 20 74 72 75 6e o subtypes: trun
2490: 6b 20 70 61 67 65 73 20 61 6e 64 20 6c 65 61 66 k pages and leaf
24a0: 20 70 61 67 65 73 2e 20 20 54 68 65 0a 2a 2a 20 pages. The.**
24b0: 66 69 6c 65 20 68 65 61 64 65 72 20 70 6f 69 6e file header poin
24c0: 74 73 20 74 6f 20 74 68 65 20 66 69 72 73 74 20 ts to the first
24d0: 69 6e 20 61 20 6c 69 6e 6b 65 64 20 6c 69 73 74 in a linked list
24e0: 20 6f 66 20 74 72 75 6e 6b 20 70 61 67 65 2e 20 of trunk page.
24f0: 20 45 61 63 68 20 74 72 75 6e 6b 0a 2a 2a 20 70 Each trunk.** p
2500: 61 67 65 20 70 6f 69 6e 74 73 20 74 6f 20 6d 75 age points to mu
2510: 6c 74 69 70 6c 65 20 6c 65 61 66 20 70 61 67 65 ltiple leaf page
2520: 73 2e 20 20 54 68 65 20 63 6f 6e 74 65 6e 74 20 s. The content
2530: 6f 66 20 61 20 6c 65 61 66 20 70 61 67 65 20 69 of a leaf page i
2540: 73 0a 2a 2a 20 75 6e 73 70 65 63 69 66 69 65 64 s.** unspecified
2550: 2e 20 20 41 20 74 72 75 6e 6b 20 70 61 67 65 20 . A trunk page
2560: 6c 6f 6f 6b 73 20 6c 69 6b 65 20 74 68 69 73 3a looks like this:
2570: 0a 2a 2a 0a 2a 2a 20 20 20 20 53 49 5a 45 20 20 .**.** SIZE
2580: 20 20 44 45 53 43 52 49 50 54 49 4f 4e 0a 2a 2a DESCRIPTION.**
2590: 20 20 20 20 20 20 34 20 20 20 20 20 50 61 67 65 4 Page
25a0: 20 6e 75 6d 62 65 72 20 6f 66 20 6e 65 78 74 20 number of next
25b0: 74 72 75 6e 6b 20 70 61 67 65 0a 2a 2a 20 20 20 trunk page.**
25c0: 20 20 20 34 20 20 20 20 20 4e 75 6d 62 65 72 20 4 Number
25d0: 6f 66 20 6c 65 61 66 20 70 6f 69 6e 74 65 72 73 of leaf pointers
25e0: 20 6f 6e 20 74 68 69 73 20 70 61 67 65 0a 2a 2a on this page.**
25f0: 20 20 20 20 20 20 2a 20 20 20 20 20 7a 65 72 6f * zero
2600: 20 6f 72 20 6d 6f 72 65 20 70 61 67 65 73 20 6e or more pages n
2610: 75 6d 62 65 72 73 20 6f 66 20 6c 65 61 76 65 73 umbers of leaves
2620: 0a 2a 2f 0a 23 69 6e 63 6c 75 64 65 20 22 73 71 .*/.#include "sq
2630: 6c 69 74 65 49 6e 74 2e 68 22 0a 23 69 6e 63 6c liteInt.h".#incl
2640: 75 64 65 20 22 70 61 67 65 72 2e 68 22 0a 23 69 ude "pager.h".#i
2650: 6e 63 6c 75 64 65 20 22 62 74 72 65 65 2e 68 22 nclude "btree.h"
2660: 0a 23 69 6e 63 6c 75 64 65 20 22 6f 73 2e 68 22 .#include "os.h"
2670: 0a 23 69 6e 63 6c 75 64 65 20 3c 61 73 73 65 72 .#include <asser
2680: 74 2e 68 3e 0a 0a 2f 2a 20 52 6f 75 6e 64 20 75 t.h>../* Round u
2690: 70 20 61 20 6e 75 6d 62 65 72 20 74 6f 20 74 68 p a number to th
26a0: 65 20 6e 65 78 74 20 6c 61 72 67 65 72 20 6d 75 e next larger mu
26b0: 6c 74 69 70 6c 65 20 6f 66 20 38 2e 20 20 54 68 ltiple of 8. Th
26c0: 69 73 20 69 73 20 75 73 65 64 0a 2a 2a 20 74 6f is is used.** to
26d0: 20 66 6f 72 63 65 20 38 2d 62 79 74 65 20 61 6c force 8-byte al
26e0: 69 67 6e 6d 65 6e 74 20 6f 6e 20 36 34 2d 62 69 ignment on 64-bi
26f0: 74 20 61 72 63 68 69 74 65 63 74 75 72 65 73 2e t architectures.
2700: 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 52 4f 55 4e .*/.#define ROUN
2710: 44 38 28 78 29 20 20 20 28 28 78 2b 37 29 26 7e D8(x) ((x+7)&~
2720: 37 29 0a 0a 0a 2f 2a 20 54 68 65 20 66 6f 6c 6c 7).../* The foll
2730: 6f 77 69 6e 67 20 76 61 6c 75 65 20 69 73 20 74 owing value is t
2740: 68 65 20 6d 61 78 69 6d 75 6d 20 63 65 6c 6c 20 he maximum cell
2750: 73 69 7a 65 20 61 73 73 75 6d 69 6e 67 20 61 20 size assuming a
2760: 6d 61 78 69 6d 75 6d 20 70 61 67 65 0a 2a 2a 20 maximum page.**
2770: 73 69 7a 65 20 67 69 76 65 20 61 62 6f 76 65 2e size give above.
2780: 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 4d 58 5f 43 .*/.#define MX_C
2790: 45 4c 4c 5f 53 49 5a 45 28 70 42 74 29 20 20 28 ELL_SIZE(pBt) (
27a0: 70 42 74 2d 3e 70 61 67 65 53 69 7a 65 2d 38 29 pBt->pageSize-8)
27b0: 0a 0a 2f 2a 20 54 68 65 20 6d 61 78 69 6d 75 6d ../* The maximum
27c0: 20 6e 75 6d 62 65 72 20 6f 66 20 63 65 6c 6c 73 number of cells
27d0: 20 6f 6e 20 61 20 73 69 6e 67 6c 65 20 70 61 67 on a single pag
27e0: 65 20 6f 66 20 74 68 65 20 64 61 74 61 62 61 73 e of the databas
27f0: 65 2e 20 20 54 68 69 73 0a 2a 2a 20 61 73 73 75 e. This.** assu
2800: 6d 65 73 20 61 20 6d 69 6e 69 6d 75 6d 20 63 65 mes a minimum ce
2810: 6c 6c 20 73 69 7a 65 20 6f 66 20 33 20 62 79 74 ll size of 3 byt
2820: 65 73 2e 20 20 53 75 63 68 20 73 6d 61 6c 6c 20 es. Such small
2830: 63 65 6c 6c 73 20 77 69 6c 6c 20 62 65 0a 2a 2a cells will be.**
2840: 20 65 78 63 65 65 64 69 6e 67 6c 79 20 72 61 72 exceedingly rar
2850: 65 2c 20 62 75 74 20 74 68 65 79 20 61 72 65 20 e, but they are
2860: 70 6f 73 73 69 62 6c 65 2e 0a 2a 2f 0a 23 64 65 possible..*/.#de
2870: 66 69 6e 65 20 4d 58 5f 43 45 4c 4c 28 70 42 74 fine MX_CELL(pBt
2880: 29 20 28 28 70 42 74 2d 3e 70 61 67 65 53 69 7a ) ((pBt->pageSiz
2890: 65 2d 38 29 2f 33 29 0a 0a 2f 2a 20 46 6f 72 77 e-8)/3)../* Forw
28a0: 61 72 64 20 64 65 63 6c 61 72 61 74 69 6f 6e 73 ard declarations
28b0: 20 2a 2f 0a 74 79 70 65 64 65 66 20 73 74 72 75 */.typedef stru
28c0: 63 74 20 4d 65 6d 50 61 67 65 20 4d 65 6d 50 61 ct MemPage MemPa
28d0: 67 65 3b 0a 74 79 70 65 64 65 66 20 73 74 72 75 ge;.typedef stru
28e0: 63 74 20 42 74 4c 6f 63 6b 20 42 74 4c 6f 63 6b ct BtLock BtLock
28f0: 3b 0a 0a 2f 2a 0a 2a 2a 20 54 68 69 73 20 69 73 ;../*.** This is
2900: 20 61 20 6d 61 67 69 63 20 73 74 72 69 6e 67 20 a magic string
2910: 74 68 61 74 20 61 70 70 65 61 72 73 20 61 74 20 that appears at
2920: 74 68 65 20 62 65 67 69 6e 6e 69 6e 67 20 6f 66 the beginning of
2930: 20 65 76 65 72 79 0a 2a 2a 20 53 51 4c 69 74 65 every.** SQLite
2940: 20 64 61 74 61 62 61 73 65 20 69 6e 20 6f 72 64 database in ord
2950: 65 72 20 74 6f 20 69 64 65 6e 74 69 66 79 20 74 er to identify t
2960: 68 65 20 66 69 6c 65 20 61 73 20 61 20 72 65 61 he file as a rea
2970: 6c 20 64 61 74 61 62 61 73 65 2e 0a 2a 2a 0a 2a l database..**.*
2980: 2a 20 59 6f 75 20 63 61 6e 20 63 68 61 6e 67 65 * You can change
2990: 20 74 68 69 73 20 76 61 6c 75 65 20 61 74 20 63 this value at c
29a0: 6f 6d 70 69 6c 65 2d 74 69 6d 65 20 62 79 20 73 ompile-time by s
29b0: 70 65 63 69 66 79 69 6e 67 20 61 0a 2a 2a 20 2d pecifying a.** -
29c0: 44 53 51 4c 49 54 45 5f 46 49 4c 45 5f 48 45 41 DSQLITE_FILE_HEA
29d0: 44 45 52 3d 22 2e 2e 2e 22 20 6f 6e 20 74 68 65 DER="..." on the
29e0: 20 63 6f 6d 70 69 6c 65 72 20 63 6f 6d 6d 61 6e compiler comman
29f0: 64 2d 6c 69 6e 65 2e 20 20 54 68 65 0a 2a 2a 20 d-line. The.**
2a00: 68 65 61 64 65 72 20 6d 75 73 74 20 62 65 20 65 header must be e
2a10: 78 61 63 74 6c 79 20 31 36 20 62 79 74 65 73 20 xactly 16 bytes
2a20: 69 6e 63 6c 75 64 69 6e 67 20 74 68 65 20 7a 65 including the ze
2a30: 72 6f 2d 74 65 72 6d 69 6e 61 74 6f 72 20 73 6f ro-terminator so
2a40: 0a 2a 2a 20 74 68 65 20 73 74 72 69 6e 67 20 69 .** the string i
2a50: 74 73 65 6c 66 20 73 68 6f 75 6c 64 20 62 65 20 tself should be
2a60: 31 35 20 63 68 61 72 61 63 74 65 72 73 20 6c 6f 15 characters lo
2a70: 6e 67 2e 20 20 49 66 20 79 6f 75 20 63 68 61 6e ng. If you chan
2a80: 67 65 0a 2a 2a 20 74 68 65 20 68 65 61 64 65 72 ge.** the header
2a90: 2c 20 74 68 65 6e 20 79 6f 75 72 20 63 75 73 74 , then your cust
2aa0: 6f 6d 20 6c 69 62 72 61 72 79 20 77 69 6c 6c 20 om library will
2ab0: 6e 6f 74 20 62 65 20 61 62 6c 65 20 74 6f 20 72 not be able to r
2ac0: 65 61 64 20 0a 2a 2a 20 64 61 74 61 62 61 73 65 ead .** database
2ad0: 73 20 67 65 6e 65 72 61 74 65 64 20 62 79 20 74 s generated by t
2ae0: 68 65 20 73 74 61 6e 64 61 72 64 20 74 6f 6f 6c he standard tool
2af0: 73 20 61 6e 64 20 74 68 65 20 73 74 61 6e 64 61 s and the standa
2b00: 72 64 20 74 6f 6f 6c 73 0a 2a 2a 20 77 69 6c 6c rd tools.** will
2b10: 20 6e 6f 74 20 62 65 20 61 62 6c 65 20 74 6f 20 not be able to
2b20: 72 65 61 64 20 64 61 74 61 62 61 73 65 73 20 63 read databases c
2b30: 72 65 61 74 65 64 20 62 79 20 79 6f 75 72 20 63 reated by your c
2b40: 75 73 74 6f 6d 20 6c 69 62 72 61 72 79 2e 0a 2a ustom library..*
2b50: 2f 0a 23 69 66 6e 64 65 66 20 53 51 4c 49 54 45 /.#ifndef SQLITE
2b60: 5f 46 49 4c 45 5f 48 45 41 44 45 52 20 2f 2a 20 _FILE_HEADER /*
2b70: 31 32 33 34 35 36 37 38 39 20 31 32 33 34 35 36 123456789 123456
2b80: 20 2a 2f 0a 23 20 20 64 65 66 69 6e 65 20 53 51 */.# define SQ
2b90: 4c 49 54 45 5f 46 49 4c 45 5f 48 45 41 44 45 52 LITE_FILE_HEADER
2ba0: 20 22 53 51 4c 69 74 65 20 66 6f 72 6d 61 74 20 "SQLite format
2bb0: 33 22 0a 23 65 6e 64 69 66 0a 0a 2f 2a 0a 2a 2a 3".#endif../*.**
2bc0: 20 50 61 67 65 20 74 79 70 65 20 66 6c 61 67 73 Page type flags
2bd0: 2e 20 20 41 6e 20 4f 52 65 64 20 63 6f 6d 62 69 . An ORed combi
2be0: 6e 61 74 69 6f 6e 20 6f 66 20 74 68 65 73 65 20 nation of these
2bf0: 66 6c 61 67 73 20 61 70 70 65 61 72 20 61 73 20 flags appear as
2c00: 74 68 65 0a 2a 2a 20 66 69 72 73 74 20 62 79 74 the.** first byt
2c10: 65 20 6f 66 20 6f 6e 2d 64 69 73 6b 20 69 6d 61 e of on-disk ima
2c20: 67 65 20 6f 66 20 65 76 65 72 79 20 42 54 72 65 ge of every BTre
2c30: 65 20 70 61 67 65 2e 0a 2a 2f 0a 23 64 65 66 69 e page..*/.#defi
2c40: 6e 65 20 50 54 46 5f 49 4e 54 4b 45 59 20 20 20 ne PTF_INTKEY
2c50: 20 30 78 30 31 0a 23 64 65 66 69 6e 65 20 50 54 0x01.#define PT
2c60: 46 5f 5a 45 52 4f 44 41 54 41 20 20 30 78 30 32 F_ZERODATA 0x02
2c70: 0a 23 64 65 66 69 6e 65 20 50 54 46 5f 4c 45 41 .#define PTF_LEA
2c80: 46 44 41 54 41 20 20 30 78 30 34 0a 23 64 65 66 FDATA 0x04.#def
2c90: 69 6e 65 20 50 54 46 5f 4c 45 41 46 20 20 20 20 ine PTF_LEAF
2ca0: 20 20 30 78 30 38 0a 0a 2f 2a 0a 2a 2a 20 41 73 0x08../*.** As
2cb0: 20 65 61 63 68 20 70 61 67 65 20 6f 66 20 74 68 each page of th
2cc0: 65 20 66 69 6c 65 20 69 73 20 6c 6f 61 64 65 64 e file is loaded
2cd0: 20 69 6e 74 6f 20 6d 65 6d 6f 72 79 2c 20 61 6e into memory, an
2ce0: 20 69 6e 73 74 61 6e 63 65 20 6f 66 20 74 68 65 instance of the
2cf0: 20 66 6f 6c 6c 6f 77 69 6e 67 0a 2a 2a 20 73 74 following.** st
2d00: 72 75 63 74 75 72 65 20 69 73 20 61 70 70 65 6e ructure is appen
2d10: 64 65 64 20 61 6e 64 20 69 6e 69 74 69 61 6c 69 ded and initiali
2d20: 7a 65 64 20 74 6f 20 7a 65 72 6f 2e 20 20 54 68 zed to zero. Th
2d30: 69 73 20 73 74 72 75 63 74 75 72 65 20 73 74 6f is structure sto
2d40: 72 65 73 0a 2a 2a 20 69 6e 66 6f 72 6d 61 74 69 res.** informati
2d50: 6f 6e 20 61 62 6f 75 74 20 74 68 65 20 70 61 67 on about the pag
2d60: 65 20 74 68 61 74 20 69 73 20 64 65 63 6f 64 65 e that is decode
2d70: 64 20 66 72 6f 6d 20 74 68 65 20 72 61 77 20 66 d from the raw f
2d80: 69 6c 65 20 70 61 67 65 2e 0a 2a 2a 0a 2a 2a 20 ile page..**.**
2d90: 54 68 65 20 70 50 61 72 65 6e 74 20 66 69 65 6c The pParent fiel
2da0: 64 20 70 6f 69 6e 74 73 20 62 61 63 6b 20 74 6f d points back to
2db0: 20 74 68 65 20 70 61 72 65 6e 74 20 70 61 67 65 the parent page
2dc0: 2e 20 20 54 68 69 73 20 61 6c 6c 6f 77 73 20 75 . This allows u
2dd0: 73 20 74 6f 0a 2a 2a 20 77 61 6c 6b 20 75 70 20 s to.** walk up
2de0: 74 68 65 20 42 54 72 65 65 20 66 72 6f 6d 20 61 the BTree from a
2df0: 6e 79 20 6c 65 61 66 20 74 6f 20 74 68 65 20 72 ny leaf to the r
2e00: 6f 6f 74 2e 20 20 43 61 72 65 20 6d 75 73 74 20 oot. Care must
2e10: 62 65 20 74 61 6b 65 6e 20 74 6f 0a 2a 2a 20 75 be taken to.** u
2e20: 6e 72 65 66 28 29 20 74 68 65 20 70 61 72 65 6e nref() the paren
2e30: 74 20 70 61 67 65 20 70 6f 69 6e 74 65 72 20 77 t page pointer w
2e40: 68 65 6e 20 74 68 69 73 20 70 61 67 65 20 69 73 hen this page is
2e50: 20 6e 6f 20 6c 6f 6e 67 65 72 20 72 65 66 65 72 no longer refer
2e60: 65 6e 63 65 64 2e 0a 2a 2a 20 54 68 65 20 70 61 enced..** The pa
2e70: 67 65 44 65 73 74 72 75 63 74 6f 72 28 29 20 72 geDestructor() r
2e80: 6f 75 74 69 6e 65 20 68 61 6e 64 6c 65 73 20 74 outine handles t
2e90: 68 61 74 20 63 68 6f 72 65 2e 0a 2a 2a 0a 2a 2a hat chore..**.**
2ea0: 20 41 63 63 65 73 73 20 74 6f 20 61 6c 6c 20 66 Access to all f
2eb0: 69 65 6c 64 73 20 6f 66 20 74 68 69 73 20 73 74 ields of this st
2ec0: 72 75 63 74 75 72 65 20 69 73 20 63 6f 6e 74 72 ructure is contr
2ed0: 6f 6c 6c 65 64 20 62 79 20 74 68 65 20 6d 75 74 olled by the mut
2ee0: 65 78 0a 2a 2a 20 73 74 6f 72 65 64 20 69 6e 20 ex.** stored in
2ef0: 4d 65 6d 50 61 67 65 2e 70 42 74 2d 3e 6d 75 74 MemPage.pBt->mut
2f00: 65 78 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 4d 65 ex..*/.struct Me
2f10: 6d 50 61 67 65 20 7b 0a 20 20 75 38 20 69 73 49 mPage {. u8 isI
2f20: 6e 69 74 3b 20 20 20 20 20 20 20 20 20 20 20 2f nit; /
2f30: 2a 20 54 72 75 65 20 69 66 20 70 72 65 76 69 6f * True if previo
2f40: 75 73 6c 79 20 69 6e 69 74 69 61 6c 69 7a 65 64 usly initialized
2f50: 2e 20 4d 55 53 54 20 42 45 20 46 49 52 53 54 21 . MUST BE FIRST!
2f60: 20 2a 2f 0a 20 20 75 38 20 69 64 78 53 68 69 66 */. u8 idxShif
2f70: 74 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 54 72 t; /* Tr
2f80: 75 65 20 69 66 20 43 65 6c 6c 20 69 6e 64 69 63 ue if Cell indic
2f90: 65 73 20 68 61 76 65 20 63 68 61 6e 67 65 64 20 es have changed
2fa0: 2a 2f 0a 20 20 75 38 20 6e 4f 76 65 72 66 6c 6f */. u8 nOverflo
2fb0: 77 3b 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d w; /* Num
2fc0: 62 65 72 20 6f 66 20 6f 76 65 72 66 6c 6f 77 20 ber of overflow
2fd0: 63 65 6c 6c 20 62 6f 64 69 65 73 20 69 6e 20 61 cell bodies in a
2fe0: 43 65 6c 6c 5b 5d 20 2a 2f 0a 20 20 75 38 20 69 Cell[] */. u8 i
2ff0: 6e 74 4b 65 79 3b 20 20 20 20 20 20 20 20 20 20 ntKey;
3000: 20 2f 2a 20 54 72 75 65 20 69 66 20 69 6e 74 6b /* True if intk
3010: 65 79 20 66 6c 61 67 20 69 73 20 73 65 74 20 2a ey flag is set *
3020: 2f 0a 20 20 75 38 20 6c 65 61 66 3b 20 20 20 20 /. u8 leaf;
3030: 20 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65 /* True
3040: 20 69 66 20 6c 65 61 66 20 66 6c 61 67 20 69 73 if leaf flag is
3050: 20 73 65 74 20 2a 2f 0a 20 20 75 38 20 7a 65 72 set */. u8 zer
3060: 6f 44 61 74 61 3b 20 20 20 20 20 20 20 20 20 2f oData; /
3070: 2a 20 54 72 75 65 20 69 66 20 74 61 62 6c 65 20 * True if table
3080: 73 74 6f 72 65 73 20 6b 65 79 73 20 6f 6e 6c 79 stores keys only
3090: 20 2a 2f 0a 20 20 75 38 20 6c 65 61 66 44 61 74 */. u8 leafDat
30a0: 61 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 54 72 a; /* Tr
30b0: 75 65 20 69 66 20 74 61 62 6c 65 73 20 73 74 6f ue if tables sto
30c0: 72 65 73 20 64 61 74 61 20 6f 6e 20 6c 65 61 76 res data on leav
30d0: 65 73 20 6f 6e 6c 79 20 2a 2f 0a 20 20 75 38 20 es only */. u8
30e0: 68 61 73 44 61 74 61 3b 20 20 20 20 20 20 20 20 hasData;
30f0: 20 20 2f 2a 20 54 72 75 65 20 69 66 20 74 68 69 /* True if thi
3100: 73 20 70 61 67 65 20 73 74 6f 72 65 73 20 64 61 s page stores da
3110: 74 61 20 2a 2f 0a 20 20 75 38 20 68 64 72 4f 66 ta */. u8 hdrOf
3120: 66 73 65 74 3b 20 20 20 20 20 20 20 20 2f 2a 20 fset; /*
3130: 31 30 30 20 66 6f 72 20 70 61 67 65 20 31 2e 20 100 for page 1.
3140: 20 30 20 6f 74 68 65 72 77 69 73 65 20 2a 2f 0a 0 otherwise */.
3150: 20 20 75 38 20 63 68 69 6c 64 50 74 72 53 69 7a u8 childPtrSiz
3160: 65 3b 20 20 20 20 20 2f 2a 20 30 20 69 66 20 6c e; /* 0 if l
3170: 65 61 66 3d 3d 31 2e 20 20 34 20 69 66 20 6c 65 eaf==1. 4 if le
3180: 61 66 3d 3d 30 20 2a 2f 0a 20 20 75 31 36 20 6d af==0 */. u16 m
3190: 61 78 4c 6f 63 61 6c 3b 20 20 20 20 20 20 20 20 axLocal;
31a0: 2f 2a 20 43 6f 70 79 20 6f 66 20 42 74 53 68 61 /* Copy of BtSha
31b0: 72 65 64 2e 6d 61 78 4c 6f 63 61 6c 20 6f 72 20 red.maxLocal or
31c0: 42 74 53 68 61 72 65 64 2e 6d 61 78 4c 65 61 66 BtShared.maxLeaf
31d0: 20 2a 2f 0a 20 20 75 31 36 20 6d 69 6e 4c 6f 63 */. u16 minLoc
31e0: 61 6c 3b 20 20 20 20 20 20 20 20 2f 2a 20 43 6f al; /* Co
31f0: 70 79 20 6f 66 20 42 74 53 68 61 72 65 64 2e 6d py of BtShared.m
3200: 69 6e 4c 6f 63 61 6c 20 6f 72 20 42 74 53 68 61 inLocal or BtSha
3210: 72 65 64 2e 6d 69 6e 4c 65 61 66 20 2a 2f 0a 20 red.minLeaf */.
3220: 20 75 31 36 20 63 65 6c 6c 4f 66 66 73 65 74 3b u16 cellOffset;
3230: 20 20 20 20 20 20 2f 2a 20 49 6e 64 65 78 20 69 /* Index i
3240: 6e 20 61 44 61 74 61 20 6f 66 20 66 69 72 73 74 n aData of first
3250: 20 63 65 6c 6c 20 70 6f 69 6e 74 65 72 20 2a 2f cell pointer */
3260: 0a 20 20 75 31 36 20 69 64 78 50 61 72 65 6e 74 . u16 idxParent
3270: 3b 20 20 20 20 20 20 20 2f 2a 20 49 6e 64 65 78 ; /* Index
3280: 20 69 6e 20 70 61 72 65 6e 74 20 6f 66 20 74 68 in parent of th
3290: 69 73 20 6e 6f 64 65 20 2a 2f 0a 20 20 75 31 36 is node */. u16
32a0: 20 6e 46 72 65 65 3b 20 20 20 20 20 20 20 20 20 nFree;
32b0: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 66 /* Number of f
32c0: 72 65 65 20 62 79 74 65 73 20 6f 6e 20 74 68 65 ree bytes on the
32d0: 20 70 61 67 65 20 2a 2f 0a 20 20 75 31 36 20 6e page */. u16 n
32e0: 43 65 6c 6c 3b 20 20 20 20 20 20 20 20 20 20 20 Cell;
32f0: 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 63 65 6c /* Number of cel
3300: 6c 73 20 6f 6e 20 74 68 69 73 20 70 61 67 65 2c ls on this page,
3310: 20 6c 6f 63 61 6c 20 61 6e 64 20 6f 76 66 6c 20 local and ovfl
3320: 2a 2f 0a 20 20 73 74 72 75 63 74 20 5f 4f 76 66 */. struct _Ovf
3330: 6c 43 65 6c 6c 20 7b 20 20 20 2f 2a 20 43 65 6c lCell { /* Cel
3340: 6c 73 20 74 68 61 74 20 77 69 6c 6c 20 6e 6f 74 ls that will not
3350: 20 66 69 74 20 6f 6e 20 61 44 61 74 61 5b 5d 20 fit on aData[]
3360: 2a 2f 0a 20 20 20 20 75 38 20 2a 70 43 65 6c 6c */. u8 *pCell
3370: 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 50 6f ; /* Po
3380: 69 6e 74 65 72 73 20 74 6f 20 74 68 65 20 62 6f inters to the bo
3390: 64 79 20 6f 66 20 74 68 65 20 6f 76 65 72 66 6c dy of the overfl
33a0: 6f 77 20 63 65 6c 6c 20 2a 2f 0a 20 20 20 20 75 ow cell */. u
33b0: 31 36 20 69 64 78 3b 20 20 20 20 20 20 20 20 20 16 idx;
33c0: 20 20 20 2f 2a 20 49 6e 73 65 72 74 20 74 68 69 /* Insert thi
33d0: 73 20 63 65 6c 6c 20 62 65 66 6f 72 65 20 69 64 s cell before id
33e0: 78 2d 74 68 20 6e 6f 6e 2d 6f 76 65 72 66 6c 6f x-th non-overflo
33f0: 77 20 63 65 6c 6c 20 2a 2f 0a 20 20 7d 20 61 4f w cell */. } aO
3400: 76 66 6c 5b 35 5d 3b 0a 20 20 42 74 53 68 61 72 vfl[5];. BtShar
3410: 65 64 20 2a 70 42 74 3b 20 20 20 20 20 20 20 2f ed *pBt; /
3420: 2a 20 50 6f 69 6e 74 65 72 20 74 6f 20 42 74 53 * Pointer to BtS
3430: 68 61 72 65 64 20 74 68 61 74 20 74 68 69 73 20 hared that this
3440: 70 61 67 65 20 69 73 20 70 61 72 74 20 6f 66 20 page is part of
3450: 2a 2f 0a 20 20 75 38 20 2a 61 44 61 74 61 3b 20 */. u8 *aData;
3460: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 50 6f 69 /* Poi
3470: 6e 74 65 72 20 74 6f 20 64 69 73 6b 20 69 6d 61 nter to disk ima
3480: 67 65 20 6f 66 20 74 68 65 20 70 61 67 65 20 64 ge of the page d
3490: 61 74 61 20 2a 2f 0a 20 20 44 62 50 61 67 65 20 ata */. DbPage
34a0: 2a 70 44 62 50 61 67 65 3b 20 20 20 20 20 2f 2a *pDbPage; /*
34b0: 20 50 61 67 65 72 20 70 61 67 65 20 68 61 6e 64 Pager page hand
34c0: 6c 65 20 2a 2f 0a 20 20 50 67 6e 6f 20 70 67 6e le */. Pgno pgn
34d0: 6f 3b 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 o; /*
34e0: 50 61 67 65 20 6e 75 6d 62 65 72 20 66 6f 72 20 Page number for
34f0: 74 68 69 73 20 70 61 67 65 20 2a 2f 0a 20 20 4d this page */. M
3500: 65 6d 50 61 67 65 20 2a 70 50 61 72 65 6e 74 3b emPage *pParent;
3510: 20 20 20 20 2f 2a 20 54 68 65 20 70 61 72 65 6e /* The paren
3520: 74 20 6f 66 20 74 68 69 73 20 70 61 67 65 2e 20 t of this page.
3530: 20 4e 55 4c 4c 20 66 6f 72 20 72 6f 6f 74 20 2a NULL for root *
3540: 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 20 /.};../*.** The
3550: 69 6e 2d 6d 65 6d 6f 72 79 20 69 6d 61 67 65 20 in-memory image
3560: 6f 66 20 61 20 64 69 73 6b 20 70 61 67 65 20 68 of a disk page h
3570: 61 73 20 74 68 65 20 61 75 78 69 6c 69 61 72 79 as the auxiliary
3580: 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 61 70 70 information app
3590: 65 6e 64 65 64 0a 2a 2a 20 74 6f 20 74 68 65 20 ended.** to the
35a0: 65 6e 64 2e 20 20 45 58 54 52 41 5f 53 49 5a 45 end. EXTRA_SIZE
35b0: 20 69 73 20 74 68 65 20 6e 75 6d 62 65 72 20 6f is the number o
35c0: 66 20 62 79 74 65 73 20 6f 66 20 73 70 61 63 65 f bytes of space
35d0: 20 6e 65 65 64 65 64 20 74 6f 20 68 6f 6c 64 0a needed to hold.
35e0: 2a 2a 20 74 68 61 74 20 65 78 74 72 61 20 69 6e ** that extra in
35f0: 66 6f 72 6d 61 74 69 6f 6e 2e 0a 2a 2f 0a 23 64 formation..*/.#d
3600: 65 66 69 6e 65 20 45 58 54 52 41 5f 53 49 5a 45 efine EXTRA_SIZE
3610: 20 73 69 7a 65 6f 66 28 4d 65 6d 50 61 67 65 29 sizeof(MemPage)
3620: 0a 0a 2f 2a 20 41 20 42 74 72 65 65 20 68 61 6e ../* A Btree han
3630: 64 6c 65 0a 2a 2a 0a 2a 2a 20 41 20 64 61 74 61 dle.**.** A data
3640: 62 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 20 base connection
3650: 63 6f 6e 74 61 69 6e 73 20 61 20 70 6f 69 6e 74 contains a point
3660: 65 72 20 74 6f 20 61 6e 20 69 6e 73 74 61 6e 63 er to an instanc
3670: 65 20 6f 66 0a 2a 2a 20 74 68 69 73 20 6f 62 6a e of.** this obj
3680: 65 63 74 20 66 6f 72 20 65 76 65 72 79 20 64 61 ect for every da
3690: 74 61 62 61 73 65 20 66 69 6c 65 20 74 68 61 74 tabase file that
36a0: 20 69 74 20 68 61 73 20 6f 70 65 6e 2e 20 20 54 it has open. T
36b0: 68 69 73 20 73 74 72 75 63 74 75 72 65 0a 2a 2a his structure.**
36c0: 20 69 73 20 6f 70 61 71 75 65 20 74 6f 20 74 68 is opaque to th
36d0: 65 20 64 61 74 61 62 61 73 65 20 63 6f 6e 6e 65 e database conne
36e0: 63 74 69 6f 6e 2e 20 20 54 68 65 20 64 61 74 61 ction. The data
36f0: 62 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 20 base connection
3700: 63 61 6e 6e 6f 74 0a 2a 2a 20 73 65 65 20 74 68 cannot.** see th
3710: 65 20 69 6e 74 65 72 6e 61 6c 73 20 6f 66 20 74 e internals of t
3720: 68 69 73 20 73 74 72 75 63 74 75 72 65 20 61 6e his structure an
3730: 64 20 6f 6e 6c 79 20 64 65 61 6c 73 20 77 69 74 d only deals wit
3740: 68 20 70 6f 69 6e 74 65 72 73 20 74 6f 0a 2a 2a h pointers to.**
3750: 20 74 68 69 73 20 73 74 72 75 63 74 75 72 65 2e this structure.
3760: 0a 2a 2a 0a 2a 2a 20 46 6f 72 20 73 6f 6d 65 20 .**.** For some
3770: 64 61 74 61 62 61 73 65 20 66 69 6c 65 73 2c 20 database files,
3780: 74 68 65 20 73 61 6d 65 20 75 6e 64 65 72 6c 79 the same underly
3790: 69 6e 67 20 64 61 74 61 62 61 73 65 20 63 61 63 ing database cac
37a0: 68 65 20 6d 69 67 68 74 20 62 65 20 0a 2a 2a 20 he might be .**
37b0: 73 68 61 72 65 64 20 62 65 74 77 65 65 6e 20 6d shared between m
37c0: 75 6c 74 69 70 6c 65 20 63 6f 6e 6e 65 63 74 69 ultiple connecti
37d0: 6f 6e 73 2e 20 20 49 6e 20 74 68 61 74 20 63 61 ons. In that ca
37e0: 73 65 2c 20 65 61 63 68 20 63 6f 6e 74 65 63 74 se, each contect
37f0: 69 6f 6e 0a 2a 2a 20 68 61 73 20 69 74 20 6f 77 ion.** has it ow
3800: 6e 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 69 n pointer to thi
3810: 73 20 6f 62 6a 65 63 74 2e 20 20 42 75 74 20 65 s object. But e
3820: 61 63 68 20 69 6e 73 74 61 6e 63 65 20 6f 66 20 ach instance of
3830: 74 68 69 73 20 6f 62 6a 65 63 74 0a 2a 2a 20 70 this object.** p
3840: 6f 69 6e 74 73 20 74 6f 20 74 68 65 20 73 61 6d oints to the sam
3850: 65 20 42 74 53 68 61 72 65 64 20 6f 62 6a 65 63 e BtShared objec
3860: 74 2e 20 20 54 68 65 20 64 61 74 61 62 61 73 65 t. The database
3870: 20 63 61 63 68 65 20 61 6e 64 20 74 68 65 0a 2a cache and the.*
3880: 2a 20 73 63 68 65 6d 61 20 61 73 73 6f 63 69 61 * schema associa
3890: 74 65 64 20 77 69 74 68 20 74 68 65 20 64 61 74 ted with the dat
38a0: 61 62 61 73 65 20 66 69 6c 65 20 61 72 65 20 61 abase file are a
38b0: 6c 6c 20 63 6f 6e 74 61 69 6e 65 64 20 77 69 74 ll contained wit
38c0: 68 69 6e 0a 2a 2a 20 74 68 65 20 42 74 53 68 61 hin.** the BtSha
38d0: 72 65 64 20 6f 62 6a 65 63 74 2e 0a 2a 2a 0a 2a red object..**.*
38e0: 2a 20 41 6c 6c 20 66 69 65 6c 64 73 20 69 6e 20 * All fields in
38f0: 74 68 69 73 20 73 74 72 75 63 74 75 72 65 20 61 this structure a
3900: 72 65 20 61 63 63 65 73 73 65 64 20 75 6e 64 65 re accessed unde
3910: 72 20 74 68 65 20 73 71 6c 69 74 65 33 2e 6d 75 r the sqlite3.mu
3920: 74 65 78 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 42 tex..*/.struct B
3930: 74 72 65 65 20 7b 0a 20 20 73 71 6c 69 74 65 33 tree {. sqlite3
3940: 20 2a 70 53 71 6c 69 74 65 3b 20 20 2f 2a 20 54 *pSqlite; /* T
3950: 68 65 20 64 61 74 61 62 61 73 65 20 63 6f 6e 6e he database conn
3960: 65 63 74 69 6f 6e 20 68 6f 6c 64 69 6e 67 20 74 ection holding t
3970: 68 69 73 20 62 74 72 65 65 20 2a 2f 0a 20 20 42 his btree */. B
3980: 74 53 68 61 72 65 64 20 2a 70 42 74 3b 20 20 20 tShared *pBt;
3990: 20 20 2f 2a 20 53 68 61 72 61 62 6c 65 20 63 6f /* Sharable co
39a0: 6e 74 65 6e 74 20 6f 66 20 74 68 69 73 20 62 74 ntent of this bt
39b0: 72 65 65 20 2a 2f 0a 20 20 75 38 20 69 6e 54 72 ree */. u8 inTr
39c0: 61 6e 73 3b 20 20 20 20 20 20 20 20 2f 2a 20 54 ans; /* T
39d0: 52 41 4e 53 5f 4e 4f 4e 45 2c 20 54 52 41 4e 53 RANS_NONE, TRANS
39e0: 5f 52 45 41 44 20 6f 72 20 54 52 41 4e 53 5f 57 _READ or TRANS_W
39f0: 52 49 54 45 20 2a 2f 0a 20 20 75 38 20 73 68 61 RITE */. u8 sha
3a00: 72 61 62 6c 65 3b 20 20 20 20 20 20 20 2f 2a 20 rable; /*
3a10: 54 72 75 65 20 69 66 20 77 65 20 63 61 6e 20 73 True if we can s
3a20: 68 61 72 65 20 70 42 74 20 77 69 74 68 20 6f 74 hare pBt with ot
3a30: 68 65 72 20 70 53 71 6c 69 74 65 20 2a 2f 0a 20 her pSqlite */.
3a40: 20 75 38 20 6c 6f 63 6b 65 64 3b 20 20 20 20 20 u8 locked;
3a50: 20 20 20 20 2f 2a 20 54 72 75 65 20 69 66 20 70 /* True if p
3a60: 53 71 6c 69 74 65 20 63 75 72 72 65 6e 74 6c 79 Sqlite currently
3a70: 20 68 61 73 20 70 42 74 20 6c 6f 63 6b 65 64 20 has pBt locked
3a80: 2a 2f 0a 20 20 69 6e 74 20 77 61 6e 74 54 6f 4c */. int wantToL
3a90: 6f 63 6b 3b 20 20 20 20 2f 2a 20 4e 75 6d 62 65 ock; /* Numbe
3aa0: 72 20 6f 66 20 6e 65 73 74 65 64 20 63 61 6c 6c r of nested call
3ab0: 73 20 74 6f 20 73 71 6c 69 74 65 33 42 74 72 65 s to sqlite3Btre
3ac0: 65 45 6e 74 65 72 28 29 20 2a 2f 0a 20 20 42 74 eEnter() */. Bt
3ad0: 72 65 65 20 2a 70 4e 65 78 74 3b 20 20 20 20 20 ree *pNext;
3ae0: 20 2f 2a 20 4c 69 73 74 20 6f 66 20 42 74 72 65 /* List of Btre
3af0: 65 73 20 77 69 74 68 20 74 68 65 20 73 61 6d 65 es with the same
3b00: 20 70 53 71 6c 69 74 65 20 76 61 6c 75 65 20 2a pSqlite value *
3b10: 2f 0a 20 20 42 74 72 65 65 20 2a 70 50 72 65 76 /. Btree *pPrev
3b20: 3b 20 20 20 20 20 20 2f 2a 20 42 61 63 6b 20 70 ; /* Back p
3b30: 6f 69 6e 74 65 72 20 6f 66 20 74 68 65 20 73 61 ointer of the sa
3b40: 6d 65 20 6c 69 73 74 20 2a 2f 0a 7d 3b 0a 0a 2f me list */.};../
3b50: 2a 0a 2a 2a 20 42 74 72 65 65 2e 69 6e 54 72 61 *.** Btree.inTra
3b60: 6e 73 20 6d 61 79 20 74 61 6b 65 20 6f 6e 65 20 ns may take one
3b70: 6f 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 of the following
3b80: 20 76 61 6c 75 65 73 2e 0a 2a 2a 0a 2a 2a 20 49 values..**.** I
3b90: 66 20 74 68 65 20 73 68 61 72 65 64 2d 64 61 74 f the shared-dat
3ba0: 61 20 65 78 74 65 6e 73 69 6f 6e 20 69 73 20 65 a extension is e
3bb0: 6e 61 62 6c 65 64 2c 20 74 68 65 72 65 20 6d 61 nabled, there ma
3bc0: 79 20 62 65 20 6d 75 6c 74 69 70 6c 65 20 75 73 y be multiple us
3bd0: 65 72 73 0a 2a 2a 20 6f 66 20 74 68 65 20 42 74 ers.** of the Bt
3be0: 72 65 65 20 73 74 72 75 63 74 75 72 65 2e 20 41 ree structure. A
3bf0: 74 20 6d 6f 73 74 20 6f 6e 65 20 6f 66 20 74 68 t most one of th
3c00: 65 73 65 20 6d 61 79 20 6f 70 65 6e 20 61 20 77 ese may open a w
3c10: 72 69 74 65 20 74 72 61 6e 73 61 63 74 69 6f 6e rite transaction
3c20: 2c 0a 2a 2a 20 62 75 74 20 61 6e 79 20 6e 75 6d ,.** but any num
3c30: 62 65 72 20 6d 61 79 20 68 61 76 65 20 61 63 74 ber may have act
3c40: 69 76 65 20 72 65 61 64 20 74 72 61 6e 73 61 63 ive read transac
3c50: 74 69 6f 6e 73 2e 0a 2a 2f 0a 23 64 65 66 69 6e tions..*/.#defin
3c60: 65 20 54 52 41 4e 53 5f 4e 4f 4e 45 20 20 30 0a e TRANS_NONE 0.
3c70: 23 64 65 66 69 6e 65 20 54 52 41 4e 53 5f 52 45 #define TRANS_RE
3c80: 41 44 20 20 31 0a 23 64 65 66 69 6e 65 20 54 52 AD 1.#define TR
3c90: 41 4e 53 5f 57 52 49 54 45 20 32 0a 0a 2f 2a 0a ANS_WRITE 2../*.
3ca0: 2a 2a 20 41 6e 20 69 6e 73 74 61 6e 63 65 20 6f ** An instance o
3cb0: 66 20 74 68 69 73 20 6f 62 6a 65 63 74 20 72 65 f this object re
3cc0: 70 72 65 73 65 6e 74 73 20 61 20 73 69 6e 67 6c presents a singl
3cd0: 65 20 64 61 74 61 62 61 73 65 20 66 69 6c 65 2e e database file.
3ce0: 0a 2a 2a 20 0a 2a 2a 20 41 20 73 69 6e 67 6c 65 .** .** A single
3cf0: 20 64 61 74 61 62 61 73 65 20 66 69 6c 65 20 63 database file c
3d00: 61 6e 20 62 65 20 69 6e 20 75 73 65 20 61 73 20 an be in use as
3d10: 74 68 65 20 73 61 6d 65 20 74 69 6d 65 20 62 79 the same time by
3d20: 20 74 77 6f 0a 2a 2a 20 6f 72 20 6d 6f 72 65 20 two.** or more
3d30: 64 61 74 61 62 61 73 65 20 63 6f 6e 6e 65 63 74 database connect
3d40: 69 6f 6e 73 2e 20 20 57 68 65 6e 20 74 77 6f 20 ions. When two
3d50: 6f 72 20 6d 6f 72 65 20 63 6f 6e 6e 65 63 74 69 or more connecti
3d60: 6f 6e 73 20 61 72 65 0a 2a 2a 20 73 68 61 72 69 ons are.** shari
3d70: 6e 67 20 74 68 65 20 73 61 6d 65 20 64 61 74 61 ng the same data
3d80: 62 61 73 65 20 66 69 6c 65 2c 20 65 61 63 68 20 base file, each
3d90: 63 6f 6e 6e 65 63 74 69 6f 6e 20 68 61 73 20 69 connection has i
3da0: 74 20 6f 77 6e 0a 2a 2a 20 70 72 69 76 61 74 65 t own.** private
3db0: 20 42 74 72 65 65 20 6f 62 6a 65 63 74 20 66 6f Btree object fo
3dc0: 72 20 74 68 65 20 66 69 6c 65 20 61 6e 64 20 65 r the file and e
3dd0: 61 63 68 20 6f 66 20 74 68 6f 73 65 20 42 74 72 ach of those Btr
3de0: 65 65 73 20 70 6f 69 6e 74 73 0a 2a 2a 20 74 6f ees points.** to
3df0: 20 74 68 69 73 20 6f 6e 65 20 42 74 53 68 61 72 this one BtShar
3e00: 65 64 20 6f 62 6a 65 63 74 2e 20 20 42 74 53 68 ed object. BtSh
3e10: 61 72 65 64 2e 6e 52 65 66 20 69 73 20 74 68 65 ared.nRef is the
3e20: 20 6e 75 6d 62 65 72 20 6f 66 0a 2a 2a 20 63 6f number of.** co
3e30: 6e 6e 65 63 74 69 6f 6e 73 20 63 75 72 72 65 6e nnections curren
3e40: 74 6c 79 20 73 68 61 72 69 6e 67 20 74 68 69 73 tly sharing this
3e50: 20 64 61 74 61 62 61 73 65 20 66 69 6c 65 2e 0a database file..
3e60: 2a 2a 0a 2a 2a 20 46 69 65 6c 64 73 20 69 6e 20 **.** Fields in
3e70: 74 68 69 73 20 73 74 72 75 63 74 75 72 65 20 61 this structure a
3e80: 72 65 20 61 63 63 65 73 73 65 64 20 75 6e 64 65 re accessed unde
3e90: 72 20 74 68 65 20 42 74 53 68 61 72 65 64 2e 6d r the BtShared.m
3ea0: 75 74 65 78 0a 2a 2a 20 6d 75 74 65 78 2c 20 65 utex.** mutex, e
3eb0: 78 63 65 70 74 20 66 6f 72 20 6e 52 65 66 20 61 xcept for nRef a
3ec0: 6e 64 20 70 4e 65 78 74 20 77 68 69 63 68 20 61 nd pNext which a
3ed0: 72 65 20 61 63 63 65 73 73 65 64 20 75 6e 64 65 re accessed unde
3ee0: 72 20 74 68 65 0a 2a 2a 20 67 6c 6f 62 61 6c 20 r the.** global
3ef0: 53 51 4c 49 54 45 5f 4d 55 54 45 58 5f 53 54 41 SQLITE_MUTEX_STA
3f00: 54 49 43 5f 4d 41 53 54 45 52 20 6d 75 74 65 78 TIC_MASTER mutex
3f10: 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 42 74 53 68 ..*/.struct BtSh
3f20: 61 72 65 64 20 7b 0a 20 20 50 61 67 65 72 20 2a ared {. Pager *
3f30: 70 50 61 67 65 72 3b 20 20 20 20 20 20 20 20 2f pPager; /
3f40: 2a 20 54 68 65 20 70 61 67 65 20 63 61 63 68 65 * The page cache
3f50: 20 2a 2f 0a 20 20 42 74 43 75 72 73 6f 72 20 2a */. BtCursor *
3f60: 70 43 75 72 73 6f 72 3b 20 20 20 20 2f 2a 20 41 pCursor; /* A
3f70: 20 6c 69 73 74 20 6f 66 20 61 6c 6c 20 6f 70 65 list of all ope
3f80: 6e 20 63 75 72 73 6f 72 73 20 2a 2f 0a 20 20 4d n cursors */. M
3f90: 65 6d 50 61 67 65 20 2a 70 50 61 67 65 31 3b 20 emPage *pPage1;
3fa0: 20 20 20 20 20 2f 2a 20 46 69 72 73 74 20 70 61 /* First pa
3fb0: 67 65 20 6f 66 20 74 68 65 20 64 61 74 61 62 61 ge of the databa
3fc0: 73 65 20 2a 2f 0a 20 20 75 38 20 69 6e 53 74 6d se */. u8 inStm
3fd0: 74 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a t; /*
3fe0: 20 54 72 75 65 20 69 66 20 77 65 20 61 72 65 20 True if we are
3ff0: 69 6e 20 61 20 73 74 61 74 65 6d 65 6e 74 20 73 in a statement s
4000: 75 62 74 72 61 6e 73 61 63 74 69 6f 6e 20 2a 2f ubtransaction */
4010: 0a 20 20 75 38 20 72 65 61 64 4f 6e 6c 79 3b 20 . u8 readOnly;
4020: 20 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65 /* True
4030: 20 69 66 20 74 68 65 20 75 6e 64 65 72 6c 79 69 if the underlyi
4040: 6e 67 20 66 69 6c 65 20 69 73 20 72 65 61 64 6f ng file is reado
4050: 6e 6c 79 20 2a 2f 0a 20 20 75 38 20 6d 61 78 45 nly */. u8 maxE
4060: 6d 62 65 64 46 72 61 63 3b 20 20 20 20 20 20 2f mbedFrac; /
4070: 2a 20 4d 61 78 69 6d 75 6d 20 70 61 79 6c 6f 61 * Maximum payloa
4080: 64 20 61 73 20 25 20 6f 66 20 74 6f 74 61 6c 20 d as % of total
4090: 70 61 67 65 20 73 69 7a 65 20 2a 2f 0a 20 20 75 page size */. u
40a0: 38 20 6d 69 6e 45 6d 62 65 64 46 72 61 63 3b 20 8 minEmbedFrac;
40b0: 20 20 20 20 20 2f 2a 20 4d 69 6e 69 6d 75 6d 20 /* Minimum
40c0: 70 61 79 6c 6f 61 64 20 61 73 20 25 20 6f 66 20 payload as % of
40d0: 74 6f 74 61 6c 20 70 61 67 65 20 73 69 7a 65 20 total page size
40e0: 2a 2f 0a 20 20 75 38 20 6d 69 6e 4c 65 61 66 46 */. u8 minLeafF
40f0: 72 61 63 3b 20 20 20 20 20 20 20 2f 2a 20 4d 69 rac; /* Mi
4100: 6e 69 6d 75 6d 20 6c 65 61 66 20 70 61 79 6c 6f nimum leaf paylo
4110: 61 64 20 61 73 20 25 20 6f 66 20 74 6f 74 61 6c ad as % of total
4120: 20 70 61 67 65 20 73 69 7a 65 20 2a 2f 0a 20 20 page size */.
4130: 75 38 20 70 61 67 65 53 69 7a 65 46 69 78 65 64 u8 pageSizeFixed
4140: 3b 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69 66 ; /* True if
4150: 20 74 68 65 20 70 61 67 65 20 73 69 7a 65 20 63 the page size c
4160: 61 6e 20 6e 6f 20 6c 6f 6e 67 65 72 20 62 65 20 an no longer be
4170: 63 68 61 6e 67 65 64 20 2a 2f 0a 23 69 66 6e 64 changed */.#ifnd
4180: 65 66 20 53 51 4c 49 54 45 5f 4f 4d 49 54 5f 41 ef SQLITE_OMIT_A
4190: 55 54 4f 56 41 43 55 55 4d 0a 20 20 75 38 20 61 UTOVACUUM. u8 a
41a0: 75 74 6f 56 61 63 75 75 6d 3b 20 20 20 20 20 20 utoVacuum;
41b0: 20 20 2f 2a 20 54 72 75 65 20 69 66 20 61 75 74 /* True if aut
41c0: 6f 2d 76 61 63 75 75 6d 20 69 73 20 65 6e 61 62 o-vacuum is enab
41d0: 6c 65 64 20 2a 2f 0a 20 20 75 38 20 69 6e 63 72 led */. u8 incr
41e0: 56 61 63 75 75 6d 3b 20 20 20 20 20 20 20 20 2f Vacuum; /
41f0: 2a 20 54 72 75 65 20 69 66 20 69 6e 63 72 2d 76 * True if incr-v
4200: 61 63 75 75 6d 20 69 73 20 65 6e 61 62 6c 65 64 acuum is enabled
4210: 20 2a 2f 0a 20 20 50 67 6e 6f 20 6e 54 72 75 6e */. Pgno nTrun
4220: 63 3b 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e c; /* N
4230: 6f 6e 2d 7a 65 72 6f 20 69 66 20 74 68 65 20 64 on-zero if the d
4240: 62 20 77 69 6c 6c 20 62 65 20 74 72 75 6e 63 61 b will be trunca
4250: 74 65 64 20 28 69 6e 63 72 20 76 61 63 75 75 6d ted (incr vacuum
4260: 29 20 2a 2f 0a 23 65 6e 64 69 66 0a 20 20 75 31 ) */.#endif. u1
4270: 36 20 70 61 67 65 53 69 7a 65 3b 20 20 20 20 20 6 pageSize;
4280: 20 20 20 20 2f 2a 20 54 6f 74 61 6c 20 6e 75 6d /* Total num
4290: 62 65 72 20 6f 66 20 62 79 74 65 73 20 6f 6e 20 ber of bytes on
42a0: 61 20 70 61 67 65 20 2a 2f 0a 20 20 75 31 36 20 a page */. u16
42b0: 75 73 61 62 6c 65 53 69 7a 65 3b 20 20 20 20 20 usableSize;
42c0: 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 75 /* Number of u
42d0: 73 61 62 6c 65 20 62 79 74 65 73 20 6f 6e 20 65 sable bytes on e
42e0: 61 63 68 20 70 61 67 65 20 2a 2f 0a 20 20 69 6e ach page */. in
42f0: 74 20 6d 61 78 4c 6f 63 61 6c 3b 20 20 20 20 20 t maxLocal;
4300: 20 20 20 20 2f 2a 20 4d 61 78 69 6d 75 6d 20 6c /* Maximum l
4310: 6f 63 61 6c 20 70 61 79 6c 6f 61 64 20 69 6e 20 ocal payload in
4320: 6e 6f 6e 2d 4c 45 41 46 44 41 54 41 20 74 61 62 non-LEAFDATA tab
4330: 6c 65 73 20 2a 2f 0a 20 20 69 6e 74 20 6d 69 6e les */. int min
4340: 4c 6f 63 61 6c 3b 20 20 20 20 20 20 20 20 20 2f Local; /
4350: 2a 20 4d 69 6e 69 6d 75 6d 20 6c 6f 63 61 6c 20 * Minimum local
4360: 70 61 79 6c 6f 61 64 20 69 6e 20 6e 6f 6e 2d 4c payload in non-L
4370: 45 41 46 44 41 54 41 20 74 61 62 6c 65 73 20 2a EAFDATA tables *
4380: 2f 0a 20 20 69 6e 74 20 6d 61 78 4c 65 61 66 3b /. int maxLeaf;
4390: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4d 61 78 /* Max
43a0: 69 6d 75 6d 20 6c 6f 63 61 6c 20 70 61 79 6c 6f imum local paylo
43b0: 61 64 20 69 6e 20 61 20 4c 45 41 46 44 41 54 41 ad in a LEAFDATA
43c0: 20 74 61 62 6c 65 20 2a 2f 0a 20 20 69 6e 74 20 table */. int
43d0: 6d 69 6e 4c 65 61 66 3b 20 20 20 20 20 20 20 20 minLeaf;
43e0: 20 20 2f 2a 20 4d 69 6e 69 6d 75 6d 20 6c 6f 63 /* Minimum loc
43f0: 61 6c 20 70 61 79 6c 6f 61 64 20 69 6e 20 61 20 al payload in a
4400: 4c 45 41 46 44 41 54 41 20 74 61 62 6c 65 20 2a LEAFDATA table *
4410: 2f 0a 20 20 42 75 73 79 48 61 6e 64 6c 65 72 20 /. BusyHandler
4420: 2a 70 42 75 73 79 48 61 6e 64 6c 65 72 3b 20 20 *pBusyHandler;
4430: 20 2f 2a 20 43 61 6c 6c 62 61 63 6b 20 66 6f 72 /* Callback for
4440: 20 77 68 65 6e 20 74 68 65 72 65 20 69 73 20 6c when there is l
4450: 6f 63 6b 20 63 6f 6e 74 65 6e 74 69 6f 6e 20 2a ock contention *
4460: 2f 0a 20 20 75 38 20 69 6e 54 72 61 6e 73 61 63 /. u8 inTransac
4470: 74 69 6f 6e 3b 20 20 20 20 20 2f 2a 20 54 72 61 tion; /* Tra
4480: 6e 73 61 63 74 69 6f 6e 20 73 74 61 74 65 20 2a nsaction state *
4490: 2f 0a 20 20 69 6e 74 20 6e 54 72 61 6e 73 61 63 /. int nTransac
44a0: 74 69 6f 6e 3b 20 20 20 20 20 2f 2a 20 4e 75 6d tion; /* Num
44b0: 62 65 72 20 6f 66 20 6f 70 65 6e 20 74 72 61 6e ber of open tran
44c0: 73 61 63 74 69 6f 6e 73 20 28 72 65 61 64 20 2b sactions (read +
44d0: 20 77 72 69 74 65 29 20 2a 2f 0a 20 20 76 6f 69 write) */. voi
44e0: 64 20 2a 70 53 63 68 65 6d 61 3b 20 20 20 20 20 d *pSchema;
44f0: 20 20 20 2f 2a 20 50 6f 69 6e 74 65 72 20 74 6f /* Pointer to
4500: 20 73 70 61 63 65 20 61 6c 6c 6f 63 61 74 65 64 space allocated
4510: 20 62 79 20 73 71 6c 69 74 65 33 42 74 72 65 65 by sqlite3Btree
4520: 53 63 68 65 6d 61 28 29 20 2a 2f 0a 20 20 76 6f Schema() */. vo
4530: 69 64 20 28 2a 78 46 72 65 65 53 63 68 65 6d 61 id (*xFreeSchema
4540: 29 28 76 6f 69 64 2a 29 3b 20 20 2f 2a 20 44 65 )(void*); /* De
4550: 73 74 72 75 63 74 6f 72 20 66 6f 72 20 42 74 53 structor for BtS
4560: 68 61 72 65 64 2e 70 53 63 68 65 6d 61 20 2a 2f hared.pSchema */
4570: 0a 20 20 73 71 6c 69 74 65 33 5f 6d 75 74 65 78 . sqlite3_mutex
4580: 20 2a 6d 75 74 65 78 3b 20 2f 2a 20 4e 6f 6e 2d *mutex; /* Non-
4590: 72 65 63 75 72 73 69 76 65 20 6d 75 74 65 78 20 recursive mutex
45a0: 72 65 71 75 69 72 65 64 20 74 6f 20 61 63 63 65 required to acce
45b0: 73 73 20 74 68 69 73 20 73 74 72 75 63 74 20 2a ss this struct *
45c0: 2f 0a 23 69 66 6e 64 65 66 20 53 51 4c 49 54 45 /.#ifndef SQLITE
45d0: 5f 4f 4d 49 54 5f 53 48 41 52 45 44 5f 43 41 43 _OMIT_SHARED_CAC
45e0: 48 45 0a 20 20 69 6e 74 20 6e 52 65 66 3b 20 20 HE. int nRef;
45f0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 /* Nu
4600: 6d 62 65 72 20 6f 66 20 72 65 66 65 72 65 6e 63 mber of referenc
4610: 65 73 20 74 6f 20 74 68 69 73 20 73 74 72 75 63 es to this struc
4620: 74 75 72 65 20 2a 2f 0a 20 20 42 74 53 68 61 72 ture */. BtShar
4630: 65 64 20 2a 70 4e 65 78 74 3b 20 20 20 20 20 20 ed *pNext;
4640: 2f 2a 20 4e 65 78 74 20 6f 6e 20 61 20 6c 69 73 /* Next on a lis
4650: 74 20 6f 66 20 73 68 61 72 61 62 6c 65 20 42 74 t of sharable Bt
4660: 53 68 61 72 65 64 20 73 74 72 75 63 74 73 20 2a Shared structs *
4670: 2f 0a 20 20 42 74 4c 6f 63 6b 20 2a 70 4c 6f 63 /. BtLock *pLoc
4680: 6b 3b 20 20 20 20 20 20 20 20 2f 2a 20 4c 69 73 k; /* Lis
4690: 74 20 6f 66 20 6c 6f 63 6b 73 20 68 65 6c 64 20 t of locks held
46a0: 6f 6e 20 74 68 69 73 20 73 68 61 72 65 64 2d 62 on this shared-b
46b0: 74 72 65 65 20 73 74 72 75 63 74 20 2a 2f 0a 23 tree struct */.#
46c0: 65 6e 64 69 66 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 endif.};../*.**
46d0: 41 6e 20 69 6e 73 74 61 6e 63 65 20 6f 66 20 74 An instance of t
46e0: 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 73 74 72 he following str
46f0: 75 63 74 75 72 65 20 69 73 20 75 73 65 64 20 74 ucture is used t
4700: 6f 20 68 6f 6c 64 20 69 6e 66 6f 72 6d 61 74 69 o hold informati
4710: 6f 6e 0a 2a 2a 20 61 62 6f 75 74 20 61 20 63 65 on.** about a ce
4720: 6c 6c 2e 20 20 54 68 65 20 70 61 72 73 65 43 65 ll. The parseCe
4730: 6c 6c 50 74 72 28 29 20 66 75 6e 63 74 69 6f 6e llPtr() function
4740: 20 66 69 6c 6c 73 20 69 6e 20 74 68 69 73 20 73 fills in this s
4750: 74 72 75 63 74 75 72 65 0a 2a 2a 20 62 61 73 65 tructure.** base
4760: 64 20 6f 6e 20 69 6e 66 6f 72 6d 61 74 69 6f 6e d on information
4770: 20 65 78 74 72 61 63 74 20 66 72 6f 6d 20 74 68 extract from th
4780: 65 20 72 61 77 20 64 69 73 6b 20 70 61 67 65 2e e raw disk page.
4790: 0a 2a 2f 0a 74 79 70 65 64 65 66 20 73 74 72 75 .*/.typedef stru
47a0: 63 74 20 43 65 6c 6c 49 6e 66 6f 20 43 65 6c 6c ct CellInfo Cell
47b0: 49 6e 66 6f 3b 0a 73 74 72 75 63 74 20 43 65 6c Info;.struct Cel
47c0: 6c 49 6e 66 6f 20 7b 0a 20 20 75 38 20 2a 70 43 lInfo {. u8 *pC
47d0: 65 6c 6c 3b 20 20 20 20 20 2f 2a 20 50 6f 69 6e ell; /* Poin
47e0: 74 65 72 20 74 6f 20 74 68 65 20 73 74 61 72 74 ter to the start
47f0: 20 6f 66 20 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 of cell content
4800: 20 2a 2f 0a 20 20 69 36 34 20 6e 4b 65 79 3b 20 */. i64 nKey;
4810: 20 20 20 20 20 2f 2a 20 54 68 65 20 6b 65 79 20 /* The key
4820: 66 6f 72 20 49 4e 54 4b 45 59 20 74 61 62 6c 65 for INTKEY table
4830: 73 2c 20 6f 72 20 6e 75 6d 62 65 72 20 6f 66 20 s, or number of
4840: 62 79 74 65 73 20 69 6e 20 6b 65 79 20 2a 2f 0a bytes in key */.
4850: 20 20 75 33 32 20 6e 44 61 74 61 3b 20 20 20 20 u32 nData;
4860: 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 62 79 /* Number of by
4870: 74 65 73 20 6f 66 20 64 61 74 61 20 2a 2f 0a 20 tes of data */.
4880: 20 75 33 32 20 6e 50 61 79 6c 6f 61 64 3b 20 20 u32 nPayload;
4890: 2f 2a 20 54 6f 74 61 6c 20 61 6d 6f 75 6e 74 20 /* Total amount
48a0: 6f 66 20 70 61 79 6c 6f 61 64 20 2a 2f 0a 20 20 of payload */.
48b0: 75 31 36 20 6e 48 65 61 64 65 72 3b 20 20 20 2f u16 nHeader; /
48c0: 2a 20 53 69 7a 65 20 6f 66 20 74 68 65 20 63 65 * Size of the ce
48d0: 6c 6c 20 63 6f 6e 74 65 6e 74 20 68 65 61 64 65 ll content heade
48e0: 72 20 69 6e 20 62 79 74 65 73 20 2a 2f 0a 20 20 r in bytes */.
48f0: 75 31 36 20 6e 4c 6f 63 61 6c 3b 20 20 20 20 2f u16 nLocal; /
4900: 2a 20 41 6d 6f 75 6e 74 20 6f 66 20 70 61 79 6c * Amount of payl
4910: 6f 61 64 20 68 65 6c 64 20 6c 6f 63 61 6c 6c 79 oad held locally
4920: 20 2a 2f 0a 20 20 75 31 36 20 69 4f 76 65 72 66 */. u16 iOverf
4930: 6c 6f 77 3b 20 2f 2a 20 4f 66 66 73 65 74 20 74 low; /* Offset t
4940: 6f 20 6f 76 65 72 66 6c 6f 77 20 70 61 67 65 20 o overflow page
4950: 6e 75 6d 62 65 72 2e 20 20 5a 65 72 6f 20 69 66 number. Zero if
4960: 20 6e 6f 20 6f 76 65 72 66 6c 6f 77 20 2a 2f 0a no overflow */.
4970: 20 20 75 31 36 20 6e 53 69 7a 65 3b 20 20 20 20 u16 nSize;
4980: 20 2f 2a 20 53 69 7a 65 20 6f 66 20 74 68 65 20 /* Size of the
4990: 63 65 6c 6c 20 63 6f 6e 74 65 6e 74 20 6f 6e 20 cell content on
49a0: 74 68 65 20 6d 61 69 6e 20 62 2d 74 72 65 65 20 the main b-tree
49b0: 70 61 67 65 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a page */.};../*.*
49c0: 2a 20 41 20 63 75 72 73 6f 72 20 69 73 20 61 20 * A cursor is a
49d0: 70 6f 69 6e 74 65 72 20 74 6f 20 61 20 70 61 72 pointer to a par
49e0: 74 69 63 75 6c 61 72 20 65 6e 74 72 79 20 77 69 ticular entry wi
49f0: 74 68 69 6e 20 61 20 70 61 72 74 69 63 75 6c 61 thin a particula
4a00: 72 0a 2a 2a 20 62 2d 74 72 65 65 20 77 69 74 68 r.** b-tree with
4a10: 69 6e 20 61 20 64 61 74 61 62 61 73 65 20 66 69 in a database fi
4a20: 6c 65 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 65 6e le..**.** The en
4a30: 74 72 79 20 69 73 20 69 64 65 6e 74 69 66 69 65 try is identifie
4a40: 64 20 62 79 20 69 74 73 20 4d 65 6d 50 61 67 65 d by its MemPage
4a50: 20 61 6e 64 20 74 68 65 20 69 6e 64 65 78 20 69 and the index i
4a60: 6e 0a 2a 2a 20 4d 65 6d 50 61 67 65 2e 61 43 65 n.** MemPage.aCe
4a70: 6c 6c 5b 5d 20 6f 66 20 74 68 65 20 65 6e 74 72 ll[] of the entr
4a80: 79 2e 0a 2a 2a 0a 2a 2a 20 57 68 65 6e 20 61 20 y..**.** When a
4a90: 73 69 6e 67 6c 65 20 64 61 74 61 62 61 73 65 20 single database
4aa0: 66 69 6c 65 20 63 61 6e 20 73 68 61 72 65 64 20 file can shared
4ab0: 62 79 20 74 77 6f 20 6d 6f 72 65 20 64 61 74 61 by two more data
4ac0: 62 61 73 65 20 63 6f 6e 6e 65 63 74 69 6f 6e 73 base connections
4ad0: 2c 0a 2a 2a 20 62 75 74 20 63 75 72 73 6f 72 73 ,.** but cursors
4ae0: 20 63 61 6e 6e 6f 74 20 62 65 20 73 68 61 72 65 cannot be share
4af0: 64 2e 20 20 45 61 63 68 20 63 75 72 73 6f 72 20 d. Each cursor
4b00: 69 73 20 61 73 73 6f 63 69 61 74 65 64 20 77 69 is associated wi
4b10: 74 68 20 61 0a 2a 2a 20 70 61 72 74 69 63 75 6c th a.** particul
4b20: 61 72 20 64 61 74 61 62 61 73 65 20 63 6f 6e 6e ar database conn
4b30: 65 63 74 69 6f 6e 20 69 64 65 6e 74 69 66 69 65 ection identifie
4b40: 64 20 42 74 43 75 72 73 6f 72 2e 70 42 74 72 65 d BtCursor.pBtre
4b50: 65 2e 70 53 71 6c 69 74 65 2e 0a 2a 2a 0a 2a 2a e.pSqlite..**.**
4b60: 20 46 69 65 6c 64 73 20 69 6e 20 74 68 69 73 20 Fields in this
4b70: 73 74 72 75 63 74 75 72 65 20 61 72 65 20 61 63 structure are ac
4b80: 63 65 73 73 65 64 20 75 6e 64 65 72 20 74 68 65 cessed under the
4b90: 20 42 74 53 68 61 72 65 64 2e 6d 75 74 65 78 0a BtShared.mutex.
4ba0: 2a 2a 20 6d 75 74 65 78 2e 20 20 54 68 65 20 70 ** mutex. The p
4bb0: 42 74 72 65 65 20 66 69 65 6c 64 20 69 73 20 73 Btree field is s
4bc0: 61 66 65 20 74 6f 20 61 63 63 65 73 73 20 75 6e afe to access un
4bd0: 64 65 72 20 74 68 65 0a 2a 2a 20 42 74 53 68 61 der the.** BtSha
4be0: 72 65 64 2d 3e 70 42 74 72 65 65 2d 3e 70 53 71 red->pBtree->pSq
4bf0: 6c 69 74 65 2d 3e 6d 75 74 65 78 20 6d 75 74 65 lite->mutex mute
4c00: 78 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 42 74 43 x..*/.struct BtC
4c10: 75 72 73 6f 72 20 7b 0a 20 20 42 74 72 65 65 20 ursor {. Btree
4c20: 2a 70 42 74 72 65 65 3b 20 20 20 20 20 20 20 20 *pBtree;
4c30: 20 20 20 20 2f 2a 20 54 68 65 20 42 74 72 65 65 /* The Btree
4c40: 20 74 6f 20 77 68 69 63 68 20 74 68 69 73 20 63 to which this c
4c50: 75 72 73 6f 72 20 62 65 6c 6f 6e 67 73 20 2a 2f ursor belongs */
4c60: 0a 20 20 42 74 43 75 72 73 6f 72 20 2a 70 4e 65 . BtCursor *pNe
4c70: 78 74 2c 20 2a 70 50 72 65 76 3b 20 20 2f 2a 20 xt, *pPrev; /*
4c80: 46 6f 72 6d 73 20 61 20 6c 69 6e 6b 65 64 20 6c Forms a linked l
4c90: 69 73 74 20 6f 66 20 61 6c 6c 20 63 75 72 73 6f ist of all curso
4ca0: 72 73 20 2a 2f 0a 20 20 69 6e 74 20 28 2a 78 43 rs */. int (*xC
4cb0: 6f 6d 70 61 72 65 29 28 76 6f 69 64 2a 2c 69 6e ompare)(void*,in
4cc0: 74 2c 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e t,const void*,in
4cd0: 74 2c 63 6f 6e 73 74 20 76 6f 69 64 2a 29 3b 20 t,const void*);
4ce0: 2f 2a 20 4b 65 79 20 63 6f 6d 70 20 66 75 6e 63 /* Key comp func
4cf0: 20 2a 2f 0a 20 20 76 6f 69 64 20 2a 70 41 72 67 */. void *pArg
4d00: 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 ;
4d10: 2f 2a 20 46 69 72 73 74 20 61 72 67 20 74 6f 20 /* First arg to
4d20: 78 43 6f 6d 70 61 72 65 28 29 20 2a 2f 0a 20 20 xCompare() */.
4d30: 50 67 6e 6f 20 70 67 6e 6f 52 6f 6f 74 3b 20 20 Pgno pgnoRoot;
4d40: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65 /* The
4d50: 20 72 6f 6f 74 20 70 61 67 65 20 6f 66 20 74 68 root page of th
4d60: 69 73 20 74 72 65 65 20 2a 2f 0a 20 20 4d 65 6d is tree */. Mem
4d70: 50 61 67 65 20 2a 70 50 61 67 65 3b 20 20 20 20 Page *pPage;
4d80: 20 20 20 20 20 20 20 2f 2a 20 50 61 67 65 20 74 /* Page t
4d90: 68 61 74 20 63 6f 6e 74 61 69 6e 73 20 74 68 65 hat contains the
4da0: 20 65 6e 74 72 79 20 2a 2f 0a 20 20 69 6e 74 20 entry */. int
4db0: 69 64 78 3b 20 20 20 20 20 20 20 20 20 20 20 20 idx;
4dc0: 20 20 20 20 20 20 2f 2a 20 49 6e 64 65 78 20 6f /* Index o
4dd0: 66 20 74 68 65 20 65 6e 74 72 79 20 69 6e 20 70 f the entry in p
4de0: 50 61 67 65 2d 3e 61 43 65 6c 6c 5b 5d 20 2a 2f Page->aCell[] */
4df0: 0a 20 20 43 65 6c 6c 49 6e 66 6f 20 69 6e 66 6f . CellInfo info
4e00: 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 ; /*
4e10: 41 20 70 61 72 73 65 20 6f 66 20 74 68 65 20 63 A parse of the c
4e20: 65 6c 6c 20 77 65 20 61 72 65 20 70 6f 69 6e 74 ell we are point
4e30: 69 6e 67 20 61 74 20 2a 2f 0a 20 20 75 38 20 77 ing at */. u8 w
4e40: 72 46 6c 61 67 3b 20 20 20 20 20 20 20 20 20 20 rFlag;
4e50: 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69 66 /* True if
4e60: 20 77 72 69 74 61 62 6c 65 20 2a 2f 0a 20 20 75 writable */. u
4e70: 38 20 65 53 74 61 74 65 3b 20 20 20 20 20 20 20 8 eState;
4e80: 20 20 20 20 20 20 20 20 20 2f 2a 20 4f 6e 65 20 /* One
4e90: 6f 66 20 74 68 65 20 43 55 52 53 4f 52 5f 58 58 of the CURSOR_XX
4ea0: 58 20 63 6f 6e 73 74 61 6e 74 73 20 28 73 65 65 X constants (see
4eb0: 20 62 65 6c 6f 77 29 20 2a 2f 0a 20 20 76 6f 69 below) */. voi
4ec0: 64 20 2a 70 4b 65 79 3b 20 20 20 20 20 20 2f 2a d *pKey; /*
4ed0: 20 53 61 76 65 64 20 6b 65 79 20 74 68 61 74 20 Saved key that
4ee0: 77 61 73 20 63 75 72 73 6f 72 27 73 20 6c 61 73 was cursor's las
4ef0: 74 20 6b 6e 6f 77 6e 20 70 6f 73 69 74 69 6f 6e t known position
4f00: 20 2a 2f 0a 20 20 69 36 34 20 6e 4b 65 79 3b 20 */. i64 nKey;
4f10: 20 20 20 20 20 20 20 2f 2a 20 53 69 7a 65 20 6f /* Size o
4f20: 66 20 70 4b 65 79 2c 20 6f 72 20 6c 61 73 74 20 f pKey, or last
4f30: 69 6e 74 65 67 65 72 20 6b 65 79 20 2a 2f 0a 20 integer key */.
4f40: 20 69 6e 74 20 73 6b 69 70 3b 20 20 20 20 20 20 int skip;
4f50: 20 20 2f 2a 20 28 73 6b 69 70 3c 30 29 20 2d 3e /* (skip<0) ->
4f60: 20 50 72 65 76 28 29 20 69 73 20 61 20 6e 6f 2d Prev() is a no-
4f70: 6f 70 2e 20 28 73 6b 69 70 3e 30 29 20 2d 3e 20 op. (skip>0) ->
4f80: 4e 65 78 74 28 29 20 69 73 20 2a 2f 0a 23 69 66 Next() is */.#if
4f90: 6e 64 65 66 20 53 51 4c 49 54 45 5f 4f 4d 49 54 ndef SQLITE_OMIT
4fa0: 5f 49 4e 43 52 42 4c 4f 42 0a 20 20 75 38 20 69 _INCRBLOB. u8 i
4fb0: 73 49 6e 63 72 62 6c 6f 62 48 61 6e 64 6c 65 3b sIncrblobHandle;
4fc0: 20 20 20 20 20 20 2f 2a 20 54 72 75 65 20 69 66 /* True if
4fd0: 20 74 68 69 73 20 63 75 72 73 6f 72 20 69 73 20 this cursor is
4fe0: 61 6e 20 69 6e 63 72 2e 20 69 6f 20 68 61 6e 64 an incr. io hand
4ff0: 6c 65 20 2a 2f 0a 20 20 50 67 6e 6f 20 2a 61 4f le */. Pgno *aO
5000: 76 65 72 66 6c 6f 77 3b 20 20 20 20 20 20 20 20 verflow;
5010: 20 20 2f 2a 20 43 61 63 68 65 20 6f 66 20 6f 76 /* Cache of ov
5020: 65 72 66 6c 6f 77 20 70 61 67 65 20 6c 6f 63 61 erflow page loca
5030: 74 69 6f 6e 73 20 2a 2f 0a 23 65 6e 64 69 66 0a tions */.#endif.
5040: 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 50 6f 74 65 6e 74 };../*.** Potent
5050: 69 61 6c 20 76 61 6c 75 65 73 20 66 6f 72 20 42 ial values for B
5060: 74 43 75 72 73 6f 72 2e 65 53 74 61 74 65 2e 0a tCursor.eState..
5070: 2a 2a 0a 2a 2a 20 43 55 52 53 4f 52 5f 56 41 4c **.** CURSOR_VAL
5080: 49 44 3a 0a 2a 2a 20 20 20 43 75 72 73 6f 72 20 ID:.** Cursor
5090: 70 6f 69 6e 74 73 20 74 6f 20 61 20 76 61 6c 69 points to a vali
50a0: 64 20 65 6e 74 72 79 2e 20 67 65 74 50 61 79 6c d entry. getPayl
50b0: 6f 61 64 28 29 20 65 74 63 2e 20 6d 61 79 20 62 oad() etc. may b
50c0: 65 20 63 61 6c 6c 65 64 2e 0a 2a 2a 0a 2a 2a 20 e called..**.**
50d0: 43 55 52 53 4f 52 5f 49 4e 56 41 4c 49 44 3a 0a CURSOR_INVALID:.
50e0: 2a 2a 20 20 20 43 75 72 73 6f 72 20 64 6f 65 73 ** Cursor does
50f0: 20 6e 6f 74 20 70 6f 69 6e 74 20 74 6f 20 61 20 not point to a
5100: 76 61 6c 69 64 20 65 6e 74 72 79 2e 20 54 68 69 valid entry. Thi
5110: 73 20 63 61 6e 20 68 61 70 70 65 6e 20 28 66 6f s can happen (fo
5120: 72 20 65 78 61 6d 70 6c 65 29 20 0a 2a 2a 20 20 r example) .**
5130: 20 62 65 63 61 75 73 65 20 74 68 65 20 74 61 62 because the tab
5140: 6c 65 20 69 73 20 65 6d 70 74 79 20 6f 72 20 62 le is empty or b
5150: 65 63 61 75 73 65 20 42 74 72 65 65 43 75 72 73 ecause BtreeCurs
5160: 6f 72 46 69 72 73 74 28 29 20 68 61 73 20 6e 6f orFirst() has no
5170: 74 20 62 65 65 6e 0a 2a 2a 20 20 20 63 61 6c 6c t been.** call
5180: 65 64 2e 0a 2a 2a 0a 2a 2a 20 43 55 52 53 4f 52 ed..**.** CURSOR
5190: 5f 52 45 51 55 49 52 45 53 45 45 4b 3a 0a 2a 2a _REQUIRESEEK:.**
51a0: 20 20 20 54 68 65 20 74 61 62 6c 65 20 74 68 61 The table tha
51b0: 74 20 74 68 69 73 20 63 75 72 73 6f 72 20 77 61 t this cursor wa
51c0: 73 20 6f 70 65 6e 65 64 20 6f 6e 20 73 74 69 6c s opened on stil
51d0: 6c 20 65 78 69 73 74 73 2c 20 62 75 74 20 68 61 l exists, but ha
51e0: 73 20 62 65 65 6e 20 0a 2a 2a 20 20 20 6d 6f 64 s been .** mod
51f0: 69 66 69 65 64 20 73 69 6e 63 65 20 74 68 65 20 ified since the
5200: 63 75 72 73 6f 72 20 77 61 73 20 6c 61 73 74 20 cursor was last
5210: 75 73 65 64 2e 20 54 68 65 20 63 75 72 73 6f 72 used. The cursor
5220: 20 70 6f 73 69 74 69 6f 6e 20 69 73 20 73 61 76 position is sav
5230: 65 64 0a 2a 2a 20 20 20 69 6e 20 76 61 72 69 61 ed.** in varia
5240: 62 6c 65 73 20 42 74 43 75 72 73 6f 72 2e 70 4b bles BtCursor.pK
5250: 65 79 20 61 6e 64 20 42 74 43 75 72 73 6f 72 2e ey and BtCursor.
5260: 6e 4b 65 79 2e 20 57 68 65 6e 20 61 20 63 75 72 nKey. When a cur
5270: 73 6f 72 20 69 73 20 69 6e 20 0a 2a 2a 20 20 20 sor is in .**
5280: 74 68 69 73 20 73 74 61 74 65 2c 20 72 65 73 74 this state, rest
5290: 6f 72 65 4f 72 43 6c 65 61 72 43 75 72 73 6f 72 oreOrClearCursor
52a0: 50 6f 73 69 74 69 6f 6e 28 29 20 63 61 6e 20 62 Position() can b
52b0: 65 20 63 61 6c 6c 65 64 20 74 6f 20 61 74 74 65 e called to atte
52c0: 6d 70 74 20 74 6f 0a 2a 2a 20 20 20 73 65 65 6b mpt to.** seek
52d0: 20 74 68 65 20 63 75 72 73 6f 72 20 74 6f 20 74 the cursor to t
52e0: 68 65 20 73 61 76 65 64 20 70 6f 73 69 74 69 6f he saved positio
52f0: 6e 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 43 55 n..*/.#define CU
5300: 52 53 4f 52 5f 49 4e 56 41 4c 49 44 20 20 20 20 RSOR_INVALID
5310: 20 20 20 20 20 20 20 30 0a 23 64 65 66 69 6e 65 0.#define
5320: 20 43 55 52 53 4f 52 5f 56 41 4c 49 44 20 20 20 CURSOR_VALID
5330: 20 20 20 20 20 20 20 20 20 20 31 0a 23 64 65 66 1.#def
5340: 69 6e 65 20 43 55 52 53 4f 52 5f 52 45 51 55 49 ine CURSOR_REQUI
5350: 52 45 53 45 45 4b 20 20 20 20 20 20 20 32 0a 0a RESEEK 2..
5360: 2f 2a 0a 2a 2a 20 54 68 65 20 54 52 41 43 45 20 /*.** The TRACE
5370: 6d 61 63 72 6f 20 77 69 6c 6c 20 70 72 69 6e 74 macro will print
5380: 20 68 69 67 68 2d 6c 65 76 65 6c 20 73 74 61 74 high-level stat
5390: 75 73 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 61 us information a
53a0: 62 6f 75 74 20 74 68 65 0a 2a 2a 20 62 74 72 65 bout the.** btre
53b0: 65 20 6f 70 65 72 61 74 69 6f 6e 20 77 68 65 6e e operation when
53c0: 20 74 68 65 20 67 6c 6f 62 61 6c 20 76 61 72 69 the global vari
53d0: 61 62 6c 65 20 73 71 6c 69 74 65 33 5f 62 74 72 able sqlite3_btr
53e0: 65 65 5f 74 72 61 63 65 20 69 73 0a 2a 2a 20 65 ee_trace is.** e
53f0: 6e 61 62 6c 65 64 2e 0a 2a 2f 0a 23 69 66 20 53 nabled..*/.#if S
5400: 51 4c 49 54 45 5f 54 45 53 54 0a 23 20 64 65 66 QLITE_TEST.# def
5410: 69 6e 65 20 54 52 41 43 45 28 58 29 20 20 20 69 ine TRACE(X) i
5420: 66 28 20 73 71 6c 69 74 65 33 5f 62 74 72 65 65 f( sqlite3_btree
5430: 5f 74 72 61 63 65 20 29 7b 20 70 72 69 6e 74 66 _trace ){ printf
5440: 20 58 3b 20 66 66 6c 75 73 68 28 73 74 64 6f 75 X; fflush(stdou
5450: 74 29 3b 20 7d 0a 23 65 6c 73 65 0a 23 20 64 65 t); }.#else.# de
5460: 66 69 6e 65 20 54 52 41 43 45 28 58 29 0a 23 65 fine TRACE(X).#e
5470: 6e 64 69 66 0a 0a 2f 2a 0a 2a 2a 20 52 6f 75 74 ndif../*.** Rout
5480: 69 6e 65 73 20 74 6f 20 72 65 61 64 20 61 6e 64 ines to read and
5490: 20 77 72 69 74 65 20 76 61 72 69 61 62 6c 65 2d write variable-
54a0: 6c 65 6e 67 74 68 20 69 6e 74 65 67 65 72 73 2e length integers.
54b0: 20 20 54 68 65 73 65 20 75 73 65 64 20 74 6f 0a These used to.
54c0: 2a 2a 20 62 65 20 64 65 66 69 6e 65 64 20 6c 6f ** be defined lo
54d0: 63 61 6c 6c 79 2c 20 62 75 74 20 6e 6f 77 20 77 cally, but now w
54e0: 65 20 75 73 65 20 74 68 65 20 76 61 72 69 6e 74 e use the varint
54f0: 20 72 6f 75 74 69 6e 65 73 20 69 6e 20 74 68 65 routines in the
5500: 20 75 74 69 6c 2e 63 0a 2a 2a 20 66 69 6c 65 2e util.c.** file.
5510: 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 67 65 74 56 .*/.#define getV
5520: 61 72 69 6e 74 20 20 20 20 73 71 6c 69 74 65 33 arint sqlite3
5530: 47 65 74 56 61 72 69 6e 74 0a 23 64 65 66 69 6e GetVarint.#defin
5540: 65 20 67 65 74 56 61 72 69 6e 74 33 32 28 41 2c e getVarint32(A,
5550: 42 29 20 20 28 28 2a 42 3d 2a 28 41 29 29 3c 3d B) ((*B=*(A))<=
5560: 30 78 37 66 3f 31 3a 73 71 6c 69 74 65 33 47 65 0x7f?1:sqlite3Ge
5570: 74 56 61 72 69 6e 74 33 32 28 41 2c 42 29 29 0a tVarint32(A,B)).
5580: 23 64 65 66 69 6e 65 20 70 75 74 56 61 72 69 6e #define putVarin
5590: 74 20 20 20 20 73 71 6c 69 74 65 33 50 75 74 56 t sqlite3PutV
55a0: 61 72 69 6e 74 0a 0a 2f 2a 20 54 68 65 20 64 61 arint../* The da
55b0: 74 61 62 61 73 65 20 70 61 67 65 20 74 68 65 20 tabase page the
55c0: 50 45 4e 44 49 4e 47 5f 42 59 54 45 20 6f 63 63 PENDING_BYTE occ
55d0: 75 70 69 65 73 2e 20 54 68 69 73 20 70 61 67 65 upies. This page
55e0: 20 69 73 20 6e 65 76 65 72 20 75 73 65 64 2e 0a is never used..
55f0: 2a 2a 20 54 4f 44 4f 3a 20 54 68 69 73 20 6d 61 ** TODO: This ma
5600: 63 72 6f 20 69 73 20 76 65 72 79 20 73 69 6d 69 cro is very simi
5610: 6c 61 72 79 20 74 6f 20 50 41 47 45 52 5f 4d 4a lary to PAGER_MJ
5620: 5f 50 47 4e 4f 28 29 20 69 6e 20 70 61 67 65 72 _PGNO() in pager
5630: 2e 63 2e 20 54 68 65 79 0a 2a 2a 20 73 68 6f 75 .c. They.** shou
5640: 6c 64 20 70 6f 73 73 69 62 6c 79 20 62 65 20 63 ld possibly be c
5650: 6f 6e 73 6f 6c 69 64 61 74 65 64 20 28 70 72 65 onsolidated (pre
5660: 73 75 6d 61 62 6c 79 20 69 6e 20 70 61 67 65 72 sumably in pager
5670: 2e 68 29 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 64 69 .h)..**.** If di
5680: 73 6b 20 49 2f 4f 20 69 73 20 6f 6d 69 74 74 65 sk I/O is omitte
5690: 64 20 28 6d 65 61 6e 69 6e 67 20 74 68 61 74 20 d (meaning that
56a0: 74 68 65 20 64 61 74 61 62 61 73 65 20 69 73 20 the database is
56b0: 73 74 6f 72 65 64 20 70 75 72 65 6c 79 0a 2a 2a stored purely.**
56c0: 20 69 6e 20 6d 65 6d 6f 72 79 29 20 74 68 65 6e in memory) then
56d0: 20 74 68 65 72 65 20 69 73 20 6e 6f 20 70 65 6e there is no pen
56e0: 64 69 6e 67 20 62 79 74 65 2e 0a 2a 2f 0a 23 69 ding byte..*/.#i
56f0: 66 64 65 66 20 53 51 4c 49 54 45 5f 4f 4d 49 54 fdef SQLITE_OMIT
5700: 5f 44 49 53 4b 49 4f 0a 23 20 64 65 66 69 6e 65 _DISKIO.# define
5710: 20 50 45 4e 44 49 4e 47 5f 42 59 54 45 5f 50 41 PENDING_BYTE_PA
5720: 47 45 28 70 42 74 29 20 20 30 78 37 66 66 66 66 GE(pBt) 0x7ffff
5730: 66 66 66 0a 23 65 6c 73 65 0a 23 20 64 65 66 69 fff.#else.# defi
5740: 6e 65 20 50 45 4e 44 49 4e 47 5f 42 59 54 45 5f ne PENDING_BYTE_
5750: 50 41 47 45 28 70 42 74 29 20 28 28 50 45 4e 44 PAGE(pBt) ((PEND
5760: 49 4e 47 5f 42 59 54 45 2f 28 70 42 74 29 2d 3e ING_BYTE/(pBt)->
5770: 70 61 67 65 53 69 7a 65 29 2b 31 29 0a 23 65 6e pageSize)+1).#en
5780: 64 69 66 0a 0a 2f 2a 0a 2a 2a 20 41 20 6c 69 6e dif../*.** A lin
5790: 6b 65 64 20 6c 69 73 74 20 6f 66 20 74 68 65 20 ked list of the
57a0: 66 6f 6c 6c 6f 77 69 6e 67 20 73 74 72 75 63 74 following struct
57b0: 75 72 65 73 20 69 73 20 73 74 6f 72 65 64 20 61 ures is stored a
57c0: 74 20 42 74 53 68 61 72 65 64 2e 70 4c 6f 63 6b t BtShared.pLock
57d0: 2e 0a 2a 2a 20 4c 6f 63 6b 73 20 61 72 65 20 61 ..** Locks are a
57e0: 64 64 65 64 20 28 6f 72 20 75 70 67 72 61 64 65 dded (or upgrade
57f0: 64 20 66 72 6f 6d 20 52 45 41 44 5f 4c 4f 43 4b d from READ_LOCK
5800: 20 74 6f 20 57 52 49 54 45 5f 4c 4f 43 4b 29 20 to WRITE_LOCK)
5810: 77 68 65 6e 20 61 20 63 75 72 73 6f 72 20 0a 2a when a cursor .*
5820: 2a 20 69 73 20 6f 70 65 6e 65 64 20 6f 6e 20 74 * is opened on t
5830: 68 65 20 74 61 62 6c 65 20 77 69 74 68 20 72 6f he table with ro
5840: 6f 74 20 70 61 67 65 20 42 74 53 68 61 72 65 64 ot page BtShared
5850: 2e 69 54 61 62 6c 65 2e 20 4c 6f 63 6b 73 20 61 .iTable. Locks a
5860: 72 65 20 72 65 6d 6f 76 65 64 0a 2a 2a 20 66 72 re removed.** fr
5870: 6f 6d 20 74 68 69 73 20 6c 69 73 74 20 77 68 65 om this list whe
5880: 6e 20 61 20 74 72 61 6e 73 61 63 74 69 6f 6e 20 n a transaction
5890: 69 73 20 63 6f 6d 6d 69 74 74 65 64 20 6f 72 20 is committed or
58a0: 72 6f 6c 6c 65 64 20 62 61 63 6b 2c 20 6f 72 20 rolled back, or
58b0: 77 68 65 6e 0a 2a 2a 20 61 20 62 74 72 65 65 20 when.** a btree
58c0: 68 61 6e 64 6c 65 20 69 73 20 63 6c 6f 73 65 64 handle is closed
58d0: 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 42 74 4c 6f ..*/.struct BtLo
58e0: 63 6b 20 7b 0a 20 20 42 74 72 65 65 20 2a 70 42 ck {. Btree *pB
58f0: 74 72 65 65 3b 20 20 20 20 20 20 20 20 2f 2a 20 tree; /*
5900: 42 74 72 65 65 20 68 61 6e 64 6c 65 20 68 6f 6c Btree handle hol
5910: 64 69 6e 67 20 74 68 69 73 20 6c 6f 63 6b 20 2a ding this lock *
5920: 2f 0a 20 20 50 67 6e 6f 20 69 54 61 62 6c 65 3b /. Pgno iTable;
5930: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 52 6f 6f /* Roo
5940: 74 20 70 61 67 65 20 6f 66 20 74 61 62 6c 65 20 t page of table
5950: 2a 2f 0a 20 20 75 38 20 65 4c 6f 63 6b 3b 20 20 */. u8 eLock;
5960: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 52 45 /* RE
5970: 41 44 5f 4c 4f 43 4b 20 6f 72 20 57 52 49 54 45 AD_LOCK or WRITE
5980: 5f 4c 4f 43 4b 20 2a 2f 0a 20 20 42 74 4c 6f 63 _LOCK */. BtLoc
5990: 6b 20 2a 70 4e 65 78 74 3b 20 20 20 20 20 20 20 k *pNext;
59a0: 20 2f 2a 20 4e 65 78 74 20 69 6e 20 42 74 53 68 /* Next in BtSh
59b0: 61 72 65 64 2e 70 4c 6f 63 6b 20 6c 69 73 74 20 ared.pLock list
59c0: 2a 2f 0a 7d 3b 0a 0a 2f 2a 20 43 61 6e 64 69 64 */.};../* Candid
59d0: 61 74 65 20 76 61 6c 75 65 73 20 66 6f 72 20 42 ate values for B
59e0: 74 4c 6f 63 6b 2e 65 4c 6f 63 6b 20 2a 2f 0a 23 tLock.eLock */.#
59f0: 64 65 66 69 6e 65 20 52 45 41 44 5f 4c 4f 43 4b define READ_LOCK
5a00: 20 20 20 20 20 31 0a 23 64 65 66 69 6e 65 20 57 1.#define W
5a10: 52 49 54 45 5f 4c 4f 43 4b 20 20 20 20 32 0a 0a RITE_LOCK 2..
5a20: 2f 2a 0a 2a 2a 20 54 68 65 73 65 20 6d 61 63 72 /*.** These macr
5a30: 6f 73 20 64 65 66 69 6e 65 20 74 68 65 20 6c 6f os define the lo
5a40: 63 61 74 69 6f 6e 20 6f 66 20 74 68 65 20 70 6f cation of the po
5a50: 69 6e 74 65 72 2d 6d 61 70 20 65 6e 74 72 79 20 inter-map entry
5a60: 66 6f 72 20 61 20 0a 2a 2a 20 64 61 74 61 62 61 for a .** databa
5a70: 73 65 20 70 61 67 65 2e 20 54 68 65 20 66 69 72 se page. The fir
5a80: 73 74 20 61 72 67 75 6d 65 6e 74 20 74 6f 20 65 st argument to e
5a90: 61 63 68 20 69 73 20 74 68 65 20 6e 75 6d 62 65 ach is the numbe
5aa0: 72 20 6f 66 20 75 73 61 62 6c 65 0a 2a 2a 20 62 r of usable.** b
5ab0: 79 74 65 73 20 6f 6e 20 65 61 63 68 20 70 61 67 ytes on each pag
5ac0: 65 20 6f 66 20 74 68 65 20 64 61 74 61 62 61 73 e of the databas
5ad0: 65 20 28 6f 66 74 65 6e 20 31 30 32 34 29 2e 20 e (often 1024).
5ae0: 54 68 65 20 73 65 63 6f 6e 64 20 69 73 20 74 68 The second is th
5af0: 65 0a 2a 2a 20 70 61 67 65 20 6e 75 6d 62 65 72 e.** page number
5b00: 20 74 6f 20 6c 6f 6f 6b 20 75 70 20 69 6e 20 74 to look up in t
5b10: 68 65 20 70 6f 69 6e 74 65 72 20 6d 61 70 2e 0a he pointer map..
5b20: 2a 2a 0a 2a 2a 20 50 54 52 4d 41 50 5f 50 41 47 **.** PTRMAP_PAG
5b30: 45 4e 4f 20 72 65 74 75 72 6e 73 20 74 68 65 20 ENO returns the
5b40: 64 61 74 61 62 61 73 65 20 70 61 67 65 20 6e 75 database page nu
5b50: 6d 62 65 72 20 6f 66 20 74 68 65 20 70 6f 69 6e mber of the poin
5b60: 74 65 72 2d 6d 61 70 0a 2a 2a 20 70 61 67 65 20 ter-map.** page
5b70: 74 68 61 74 20 73 74 6f 72 65 73 20 74 68 65 20 that stores the
5b80: 72 65 71 75 69 72 65 64 20 70 6f 69 6e 74 65 72 required pointer
5b90: 2e 20 50 54 52 4d 41 50 5f 50 54 52 4f 46 46 53 . PTRMAP_PTROFFS
5ba0: 45 54 20 72 65 74 75 72 6e 73 0a 2a 2a 20 74 68 ET returns.** th
5bb0: 65 20 6f 66 66 73 65 74 20 6f 66 20 74 68 65 20 e offset of the
5bc0: 72 65 71 75 65 73 74 65 64 20 6d 61 70 20 65 6e requested map en
5bd0: 74 72 79 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 74 68 try..**.** If th
5be0: 65 20 70 67 6e 6f 20 61 72 67 75 6d 65 6e 74 20 e pgno argument
5bf0: 70 61 73 73 65 64 20 74 6f 20 50 54 52 4d 41 50 passed to PTRMAP
5c00: 5f 50 41 47 45 4e 4f 20 69 73 20 61 20 70 6f 69 _PAGENO is a poi
5c10: 6e 74 65 72 2d 6d 61 70 20 70 61 67 65 2c 0a 2a nter-map page,.*
5c20: 2a 20 74 68 65 6e 20 70 67 6e 6f 20 69 73 20 72 * then pgno is r
5c30: 65 74 75 72 6e 65 64 2e 20 53 6f 20 28 70 67 6e eturned. So (pgn
5c40: 6f 3d 3d 50 54 52 4d 41 50 5f 50 41 47 45 4e 4f o==PTRMAP_PAGENO
5c50: 28 70 67 73 7a 2c 20 70 67 6e 6f 29 29 20 63 61 (pgsz, pgno)) ca
5c60: 6e 20 62 65 0a 2a 2a 20 75 73 65 64 20 74 6f 20 n be.** used to
5c70: 74 65 73 74 20 69 66 20 70 67 6e 6f 20 69 73 20 test if pgno is
5c80: 61 20 70 6f 69 6e 74 65 72 2d 6d 61 70 20 70 61 a pointer-map pa
5c90: 67 65 2e 20 50 54 52 4d 41 50 5f 49 53 50 41 47 ge. PTRMAP_ISPAG
5ca0: 45 20 69 6d 70 6c 65 6d 65 6e 74 73 0a 2a 2a 20 E implements.**
5cb0: 74 68 69 73 20 74 65 73 74 2e 0a 2a 2f 0a 23 64 this test..*/.#d
5cc0: 65 66 69 6e 65 20 50 54 52 4d 41 50 5f 50 41 47 efine PTRMAP_PAG
5cd0: 45 4e 4f 28 70 42 74 2c 20 70 67 6e 6f 29 20 70 ENO(pBt, pgno) p
5ce0: 74 72 6d 61 70 50 61 67 65 6e 6f 28 70 42 74 2c trmapPageno(pBt,
5cf0: 20 70 67 6e 6f 29 0a 23 64 65 66 69 6e 65 20 50 pgno).#define P
5d00: 54 52 4d 41 50 5f 50 54 52 4f 46 46 53 45 54 28 TRMAP_PTROFFSET(
5d10: 70 42 74 2c 20 70 67 6e 6f 29 20 28 35 2a 28 70 pBt, pgno) (5*(p
5d20: 67 6e 6f 2d 70 74 72 6d 61 70 50 61 67 65 6e 6f gno-ptrmapPageno
5d30: 28 70 42 74 2c 20 70 67 6e 6f 29 2d 31 29 29 0a (pBt, pgno)-1)).
5d40: 23 64 65 66 69 6e 65 20 50 54 52 4d 41 50 5f 49 #define PTRMAP_I
5d50: 53 50 41 47 45 28 70 42 74 2c 20 70 67 6e 6f 29 SPAGE(pBt, pgno)
5d60: 20 28 50 54 52 4d 41 50 5f 50 41 47 45 4e 4f 28 (PTRMAP_PAGENO(
5d70: 28 70 42 74 29 2c 28 70 67 6e 6f 29 29 3d 3d 28 (pBt),(pgno))==(
5d80: 70 67 6e 6f 29 29 0a 0a 2f 2a 0a 2a 2a 20 54 68 pgno))../*.** Th
5d90: 65 20 70 6f 69 6e 74 65 72 20 6d 61 70 20 69 73 e pointer map is
5da0: 20 61 20 6c 6f 6f 6b 75 70 20 74 61 62 6c 65 20 a lookup table
5db0: 74 68 61 74 20 69 64 65 6e 74 69 66 69 65 73 20 that identifies
5dc0: 74 68 65 20 70 61 72 65 6e 74 20 70 61 67 65 20 the parent page
5dd0: 66 6f 72 0a 2a 2a 20 65 61 63 68 20 63 68 69 6c for.** each chil
5de0: 64 20 70 61 67 65 20 69 6e 20 74 68 65 20 64 61 d page in the da
5df0: 74 61 62 61 73 65 20 66 69 6c 65 2e 20 20 54 68 tabase file. Th
5e00: 65 20 70 61 72 65 6e 74 20 70 61 67 65 20 69 73 e parent page is
5e10: 20 74 68 65 20 70 61 67 65 20 74 68 61 74 0a 2a the page that.*
5e20: 2a 20 63 6f 6e 74 61 69 6e 73 20 61 20 70 6f 69 * contains a poi
5e30: 6e 74 65 72 20 74 6f 20 74 68 65 20 63 68 69 6c nter to the chil
5e40: 64 2e 20 20 45 76 65 72 79 20 70 61 67 65 20 69 d. Every page i
5e50: 6e 20 74 68 65 20 64 61 74 61 62 61 73 65 20 63 n the database c
5e60: 6f 6e 74 61 69 6e 73 0a 2a 2a 20 30 20 6f 72 20 ontains.** 0 or
5e70: 31 20 70 61 72 65 6e 74 20 70 61 67 65 73 2e 20 1 parent pages.
5e80: 20 28 49 6e 20 74 68 69 73 20 63 6f 6e 74 65 78 (In this contex
5e90: 74 20 27 64 61 74 61 62 61 73 65 20 70 61 67 65 t 'database page
5ea0: 27 20 72 65 66 65 72 73 0a 2a 2a 20 74 6f 20 61 ' refers.** to a
5eb0: 6e 79 20 70 61 67 65 20 74 68 61 74 20 69 73 20 ny page that is
5ec0: 6e 6f 74 20 70 61 72 74 20 6f 66 20 74 68 65 20 not part of the
5ed0: 70 6f 69 6e 74 65 72 20 6d 61 70 20 69 74 73 65 pointer map itse
5ee0: 6c 66 2e 29 20 20 45 61 63 68 20 70 6f 69 6e 74 lf.) Each point
5ef0: 65 72 20 6d 61 70 0a 2a 2a 20 65 6e 74 72 79 20 er map.** entry
5f00: 63 6f 6e 73 69 73 74 73 20 6f 66 20 61 20 73 69 consists of a si
5f10: 6e 67 6c 65 20 62 79 74 65 20 27 74 79 70 65 27 ngle byte 'type'
5f20: 20 61 6e 64 20 61 20 34 20 62 79 74 65 20 70 61 and a 4 byte pa
5f30: 72 65 6e 74 20 70 61 67 65 20 6e 75 6d 62 65 72 rent page number
5f40: 2e 0a 2a 2a 20 54 68 65 20 50 54 52 4d 41 50 5f ..** The PTRMAP_
5f50: 58 58 58 20 69 64 65 6e 74 69 66 69 65 72 73 20 XXX identifiers
5f60: 62 65 6c 6f 77 20 61 72 65 20 74 68 65 20 76 61 below are the va
5f70: 6c 69 64 20 74 79 70 65 73 2e 0a 2a 2a 0a 2a 2a lid types..**.**
5f80: 20 54 68 65 20 70 75 72 70 6f 73 65 20 6f 66 20 The purpose of
5f90: 74 68 65 20 70 6f 69 6e 74 65 72 20 6d 61 70 20 the pointer map
5fa0: 69 73 20 74 6f 20 66 61 63 69 6c 69 74 79 20 6d is to facility m
5fb0: 6f 76 69 6e 67 20 70 61 67 65 73 20 66 72 6f 6d oving pages from
5fc0: 20 6f 6e 65 0a 2a 2a 20 70 6f 73 69 74 69 6f 6e one.** position
5fd0: 20 69 6e 20 74 68 65 20 66 69 6c 65 20 74 6f 20 in the file to
5fe0: 61 6e 6f 74 68 65 72 20 61 73 20 70 61 72 74 20 another as part
5ff0: 6f 66 20 61 75 74 6f 76 61 63 75 75 6d 2e 20 20 of autovacuum.
6000: 57 68 65 6e 20 61 20 70 61 67 65 0a 2a 2a 20 69 When a page.** i
6010: 73 20 6d 6f 76 65 64 2c 20 74 68 65 20 70 6f 69 s moved, the poi
6020: 6e 74 65 72 20 69 6e 20 69 74 73 20 70 61 72 65 nter in its pare
6030: 6e 74 20 6d 75 73 74 20 62 65 20 75 70 64 61 74 nt must be updat
6040: 65 64 20 74 6f 20 70 6f 69 6e 74 20 74 6f 20 74 ed to point to t
6050: 68 65 0a 2a 2a 20 6e 65 77 20 6c 6f 63 61 74 69 he.** new locati
6060: 6f 6e 2e 20 20 54 68 65 20 70 6f 69 6e 74 65 72 on. The pointer
6070: 20 6d 61 70 20 69 73 20 75 73 65 64 20 74 6f 20 map is used to
6080: 6c 6f 63 61 74 65 20 74 68 65 20 70 61 72 65 6e locate the paren
6090: 74 20 70 61 67 65 20 71 75 69 63 6b 6c 79 2e 0a t page quickly..
60a0: 2a 2a 0a 2a 2a 20 50 54 52 4d 41 50 5f 52 4f 4f **.** PTRMAP_ROO
60b0: 54 50 41 47 45 3a 20 54 68 65 20 64 61 74 61 62 TPAGE: The datab
60c0: 61 73 65 20 70 61 67 65 20 69 73 20 61 20 72 6f ase page is a ro
60d0: 6f 74 2d 70 61 67 65 2e 20 54 68 65 20 70 61 67 ot-page. The pag
60e0: 65 2d 6e 75 6d 62 65 72 20 69 73 20 6e 6f 74 0a e-number is not.
60f0: 2a 2a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 **
6100: 20 20 20 20 75 73 65 64 20 69 6e 20 74 68 69 73 used in this
6110: 20 63 61 73 65 2e 0a 2a 2a 0a 2a 2a 20 50 54 52 case..**.** PTR
6120: 4d 41 50 5f 46 52 45 45 50 41 47 45 3a 20 54 68 MAP_FREEPAGE: Th
6130: 65 20 64 61 74 61 62 61 73 65 20 70 61 67 65 20 e database page
6140: 69 73 20 61 6e 20 75 6e 75 73 65 64 20 28 66 72 is an unused (fr
6150: 65 65 29 20 70 61 67 65 2e 20 54 68 65 20 70 61 ee) page. The pa
6160: 67 65 2d 6e 75 6d 62 65 72 20 0a 2a 2a 20 20 20 ge-number .**
6170: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 69 i
6180: 73 20 6e 6f 74 20 75 73 65 64 20 69 6e 20 74 68 s not used in th
6190: 69 73 20 63 61 73 65 2e 0a 2a 2a 0a 2a 2a 20 50 is case..**.** P
61a0: 54 52 4d 41 50 5f 4f 56 45 52 46 4c 4f 57 31 3a TRMAP_OVERFLOW1:
61b0: 20 54 68 65 20 64 61 74 61 62 61 73 65 20 70 61 The database pa
61c0: 67 65 20 69 73 20 74 68 65 20 66 69 72 73 74 20 ge is the first
61d0: 70 61 67 65 20 69 6e 20 61 20 6c 69 73 74 20 6f page in a list o
61e0: 66 20 0a 2a 2a 20 20 20 20 20 20 20 20 20 20 20 f .**
61f0: 20 20 20 20 20 20 20 20 6f 76 65 72 66 6c 6f 77 overflow
6200: 20 70 61 67 65 73 2e 20 54 68 65 20 70 61 67 65 pages. The page
6210: 20 6e 75 6d 62 65 72 20 69 64 65 6e 74 69 66 69 number identifi
6220: 65 73 20 74 68 65 20 70 61 67 65 20 74 68 61 74 es the page that
6230: 0a 2a 2a 20 20 20 20 20 20 20 20 20 20 20 20 20 .**
6240: 20 20 20 20 20 20 63 6f 6e 74 61 69 6e 73 20 74 contains t
6250: 68 65 20 63 65 6c 6c 20 77 69 74 68 20 61 20 70 he cell with a p
6260: 6f 69 6e 74 65 72 20 74 6f 20 74 68 69 73 20 6f ointer to this o
6270: 76 65 72 66 6c 6f 77 20 70 61 67 65 2e 0a 2a 2a verflow page..**
6280: 0a 2a 2a 20 50 54 52 4d 41 50 5f 4f 56 45 52 46 .** PTRMAP_OVERF
6290: 4c 4f 57 32 3a 20 54 68 65 20 64 61 74 61 62 61 LOW2: The databa
62a0: 73 65 20 70 61 67 65 20 69 73 20 74 68 65 20 73 se page is the s
62b0: 65 63 6f 6e 64 20 6f 72 20 6c 61 74 65 72 20 70 econd or later p
62c0: 61 67 65 20 69 6e 20 61 20 6c 69 73 74 20 6f 66 age in a list of
62d0: 0a 2a 2a 20 20 20 20 20 20 20 20 20 20 20 20 20 .**
62e0: 20 20 20 20 20 20 6f 76 65 72 66 6c 6f 77 20 70 overflow p
62f0: 61 67 65 73 2e 20 54 68 65 20 70 61 67 65 2d 6e ages. The page-n
6300: 75 6d 62 65 72 20 69 64 65 6e 74 69 66 69 65 73 umber identifies
6310: 20 74 68 65 20 70 72 65 76 69 6f 75 73 0a 2a 2a the previous.**
6320: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
6330: 20 20 20 70 61 67 65 20 69 6e 20 74 68 65 20 6f page in the o
6340: 76 65 72 66 6c 6f 77 20 70 61 67 65 20 6c 69 73 verflow page lis
6350: 74 2e 0a 2a 2a 0a 2a 2a 20 50 54 52 4d 41 50 5f t..**.** PTRMAP_
6360: 42 54 52 45 45 3a 20 54 68 65 20 64 61 74 61 62 BTREE: The datab
6370: 61 73 65 20 70 61 67 65 20 69 73 20 61 20 6e 6f ase page is a no
6380: 6e 2d 72 6f 6f 74 20 62 74 72 65 65 20 70 61 67 n-root btree pag
6390: 65 2e 20 54 68 65 20 70 61 67 65 20 6e 75 6d 62 e. The page numb
63a0: 65 72 0a 2a 2a 20 20 20 20 20 20 20 20 20 20 20 er.**
63b0: 20 20 20 20 69 64 65 6e 74 69 66 69 65 73 20 74 identifies t
63c0: 68 65 20 70 61 72 65 6e 74 20 70 61 67 65 20 69 he parent page i
63d0: 6e 20 74 68 65 20 62 74 72 65 65 2e 0a 2a 2f 0a n the btree..*/.
63e0: 23 64 65 66 69 6e 65 20 50 54 52 4d 41 50 5f 52 #define PTRMAP_R
63f0: 4f 4f 54 50 41 47 45 20 31 0a 23 64 65 66 69 6e OOTPAGE 1.#defin
6400: 65 20 50 54 52 4d 41 50 5f 46 52 45 45 50 41 47 e PTRMAP_FREEPAG
6410: 45 20 32 0a 23 64 65 66 69 6e 65 20 50 54 52 4d E 2.#define PTRM
6420: 41 50 5f 4f 56 45 52 46 4c 4f 57 31 20 33 0a 23 AP_OVERFLOW1 3.#
6430: 64 65 66 69 6e 65 20 50 54 52 4d 41 50 5f 4f 56 define PTRMAP_OV
6440: 45 52 46 4c 4f 57 32 20 34 0a 23 64 65 66 69 6e ERFLOW2 4.#defin
6450: 65 20 50 54 52 4d 41 50 5f 42 54 52 45 45 20 35 e PTRMAP_BTREE 5
6460: 0a 0a 2f 2a 20 41 20 62 75 6e 63 68 20 6f 66 20 ../* A bunch of
6470: 61 73 73 65 72 74 28 29 20 73 74 61 74 65 6d 65 assert() stateme
6480: 6e 74 73 20 74 6f 20 63 68 65 63 6b 20 74 68 65 nts to check the
6490: 20 74 72 61 6e 73 61 63 74 69 6f 6e 20 73 74 61 transaction sta
64a0: 74 65 20 76 61 72 69 61 62 6c 65 73 0a 2a 2a 20 te variables.**
64b0: 6f 66 20 68 61 6e 64 6c 65 20 70 20 28 74 79 70 of handle p (typ
64c0: 65 20 42 74 72 65 65 2a 29 20 61 72 65 20 69 6e e Btree*) are in
64d0: 74 65 72 6e 61 6c 6c 79 20 63 6f 6e 73 69 73 74 ternally consist
64e0: 65 6e 74 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 20 ent..*/.#define
64f0: 62 74 72 65 65 49 6e 74 65 67 72 69 74 79 28 70 btreeIntegrity(p
6500: 29 20 5c 0a 20 20 61 73 73 65 72 74 28 20 70 2d ) \. assert( p-
6510: 3e 70 42 74 2d 3e 69 6e 54 72 61 6e 73 61 63 74 >pBt->inTransact
6520: 69 6f 6e 21 3d 54 52 41 4e 53 5f 4e 4f 4e 45 20 ion!=TRANS_NONE
6530: 7c 7c 20 70 2d 3e 70 42 74 2d 3e 6e 54 72 61 6e || p->pBt->nTran
6540: 73 61 63 74 69 6f 6e 3d 3d 30 20 29 3b 20 5c 0a saction==0 ); \.
6550: 20 20 61 73 73 65 72 74 28 20 70 2d 3e 70 42 74 assert( p->pBt
6560: 2d 3e 69 6e 54 72 61 6e 73 61 63 74 69 6f 6e 3e ->inTransaction>
6570: 3d 70 2d 3e 69 6e 54 72 61 6e 73 20 29 3b 20 0a =p->inTrans ); .
6580: 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 20 49 53 41 55 ../*.** The ISAU
6590: 54 4f 56 41 43 55 55 4d 20 6d 61 63 72 6f 20 69 TOVACUUM macro i
65a0: 73 20 75 73 65 64 20 77 69 74 68 69 6e 20 62 61 s used within ba
65b0: 6c 61 6e 63 65 5f 6e 6f 6e 72 6f 6f 74 28 29 20 lance_nonroot()
65c0: 74 6f 20 64 65 74 65 72 6d 69 6e 65 0a 2a 2a 20 to determine.**
65d0: 69 66 20 74 68 65 20 64 61 74 61 62 61 73 65 20 if the database
65e0: 73 75 70 70 6f 72 74 73 20 61 75 74 6f 2d 76 61 supports auto-va
65f0: 63 75 75 6d 20 6f 72 20 6e 6f 74 2e 20 42 65 63 cuum or not. Bec
6600: 61 75 73 65 20 69 74 20 69 73 20 75 73 65 64 0a ause it is used.
6610: 2a 2a 20 77 69 74 68 69 6e 20 61 6e 20 65 78 70 ** within an exp
6620: 72 65 73 73 69 6f 6e 20 74 68 61 74 20 69 73 20 ression that is
6630: 61 6e 20 61 72 67 75 6d 65 6e 74 20 74 6f 20 61 an argument to a
6640: 6e 6f 74 68 65 72 20 6d 61 63 72 6f 20 0a 2a 2a nother macro .**
6650: 20 28 73 71 6c 69 74 65 4d 61 6c 6c 6f 63 52 61 (sqliteMallocRa
6660: 77 29 2c 20 69 74 20 69 73 20 6e 6f 74 20 70 6f w), it is not po
6670: 73 73 69 62 6c 65 20 74 6f 20 75 73 65 20 63 6f ssible to use co
6680: 6e 64 69 74 69 6f 6e 61 6c 20 63 6f 6d 70 69 6c nditional compil
6690: 61 74 69 6f 6e 2e 0a 2a 2a 20 53 6f 2c 20 74 68 ation..** So, th
66a0: 69 73 20 6d 61 63 72 6f 20 69 73 20 64 65 66 69 is macro is defi
66b0: 6e 65 64 20 69 6e 73 74 65 61 64 2e 0a 2a 2f 0a ned instead..*/.
66c0: 23 69 66 6e 64 65 66 20 53 51 4c 49 54 45 5f 4f #ifndef SQLITE_O
66d0: 4d 49 54 5f 41 55 54 4f 56 41 43 55 55 4d 0a 23 MIT_AUTOVACUUM.#
66e0: 64 65 66 69 6e 65 20 49 53 41 55 54 4f 56 41 43 define ISAUTOVAC
66f0: 55 55 4d 20 28 70 42 74 2d 3e 61 75 74 6f 56 61 UUM (pBt->autoVa
6700: 63 75 75 6d 29 0a 23 65 6c 73 65 0a 23 64 65 66 cuum).#else.#def
6710: 69 6e 65 20 49 53 41 55 54 4f 56 41 43 55 55 4d ine ISAUTOVACUUM
6720: 20 30 0a 23 65 6e 64 69 66 0a 0a 0a 2f 2a 0a 2a 0.#endif.../*.*
6730: 2a 20 54 68 69 73 20 73 74 72 75 63 74 75 72 65 * This structure
6740: 20 69 73 20 70 61 73 73 65 64 20 61 72 6f 75 6e is passed aroun
6750: 64 20 74 68 72 6f 75 67 68 20 61 6c 6c 20 74 68 d through all th
6760: 65 20 73 61 6e 69 74 79 20 63 68 65 63 6b 69 6e e sanity checkin
6770: 67 20 72 6f 75 74 69 6e 65 73 0a 2a 2a 20 69 6e g routines.** in
6780: 20 6f 72 64 65 72 20 74 6f 20 6b 65 65 70 20 74 order to keep t
6790: 72 61 63 6b 20 6f 66 20 73 6f 6d 65 20 67 6c 6f rack of some glo
67a0: 62 61 6c 20 73 74 61 74 65 20 69 6e 66 6f 72 6d bal state inform
67b0: 61 74 69 6f 6e 2e 0a 2a 2f 0a 74 79 70 65 64 65 ation..*/.typede
67c0: 66 20 73 74 72 75 63 74 20 49 6e 74 65 67 72 69 f struct Integri
67d0: 74 79 43 6b 20 49 6e 74 65 67 72 69 74 79 43 6b tyCk IntegrityCk
67e0: 3b 0a 73 74 72 75 63 74 20 49 6e 74 65 67 72 69 ;.struct Integri
67f0: 74 79 43 6b 20 7b 0a 20 20 42 74 53 68 61 72 65 tyCk {. BtShare
6800: 64 20 2a 70 42 74 3b 20 20 20 20 2f 2a 20 54 68 d *pBt; /* Th
6810: 65 20 74 72 65 65 20 62 65 69 6e 67 20 63 68 65 e tree being che
6820: 63 6b 65 64 20 6f 75 74 20 2a 2f 0a 20 20 50 61 cked out */. Pa
6830: 67 65 72 20 2a 70 50 61 67 65 72 3b 20 20 20 20 ger *pPager;
6840: 2f 2a 20 54 68 65 20 61 73 73 6f 63 69 61 74 65 /* The associate
6850: 64 20 70 61 67 65 72 2e 20 20 41 6c 73 6f 20 61 d pager. Also a
6860: 63 63 65 73 73 69 62 6c 65 20 62 79 20 70 42 74 ccessible by pBt
6870: 2d 3e 70 50 61 67 65 72 20 2a 2f 0a 20 20 69 6e ->pPager */. in
6880: 74 20 6e 50 61 67 65 3b 20 20 20 20 20 20 20 20 t nPage;
6890: 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 70 61 67 /* Number of pag
68a0: 65 73 20 69 6e 20 74 68 65 20 64 61 74 61 62 61 es in the databa
68b0: 73 65 20 2a 2f 0a 20 20 69 6e 74 20 2a 61 6e 52 se */. int *anR
68c0: 65 66 3b 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d ef; /* Num
68d0: 62 65 72 20 6f 66 20 74 69 6d 65 73 20 65 61 63 ber of times eac
68e0: 68 20 70 61 67 65 20 69 73 20 72 65 66 65 72 65 h page is refere
68f0: 6e 63 65 64 20 2a 2f 0a 20 20 69 6e 74 20 6d 78 nced */. int mx
6900: 45 72 72 3b 20 20 20 20 20 20 20 20 2f 2a 20 53 Err; /* S
6910: 74 6f 70 20 61 63 63 75 6d 75 6c 61 74 69 6e 67 top accumulating
6920: 20 65 72 72 6f 72 73 20 77 68 65 6e 20 74 68 69 errors when thi
6930: 73 20 72 65 61 63 68 65 73 20 7a 65 72 6f 20 2a s reaches zero *
6940: 2f 0a 20 20 63 68 61 72 20 2a 7a 45 72 72 4d 73 /. char *zErrMs
6950: 67 3b 20 20 20 20 2f 2a 20 41 6e 20 65 72 72 6f g; /* An erro
6960: 72 20 6d 65 73 73 61 67 65 2e 20 20 4e 55 4c 4c r message. NULL
6970: 20 69 66 20 6e 6f 20 65 72 72 6f 72 73 20 73 65 if no errors se
6980: 65 6e 2e 20 2a 2f 0a 20 20 69 6e 74 20 6e 45 72 en. */. int nEr
6990: 72 3b 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 r; /* Nu
69a0: 6d 62 65 72 20 6f 66 20 6d 65 73 73 61 67 65 73 mber of messages
69b0: 20 77 72 69 74 74 65 6e 20 74 6f 20 7a 45 72 72 written to zErr
69c0: 4d 73 67 20 73 6f 20 66 61 72 20 2a 2f 0a 7d 3b Msg so far */.};
69d0: 0a 0a 2f 2a 0a 2a 2a 20 52 65 61 64 20 6f 72 20 ../*.** Read or
69e0: 77 72 69 74 65 20 61 20 74 77 6f 2d 20 61 6e 64 write a two- and
69f0: 20 66 6f 75 72 2d 62 79 74 65 20 62 69 67 2d 65 four-byte big-e
6a00: 6e 64 69 61 6e 20 69 6e 74 65 67 65 72 20 76 61 ndian integer va
6a10: 6c 75 65 73 2e 0a 2a 2f 0a 23 64 65 66 69 6e 65 lues..*/.#define
6a20: 20 67 65 74 32 62 79 74 65 28 78 29 20 20 20 28 get2byte(x) (
6a30: 28 78 29 5b 30 5d 3c 3c 38 20 7c 20 28 78 29 5b (x)[0]<<8 | (x)[
6a40: 31 5d 29 0a 23 64 65 66 69 6e 65 20 70 75 74 32 1]).#define put2
6a50: 62 79 74 65 28 70 2c 76 29 20 28 28 70 29 5b 30 byte(p,v) ((p)[0
6a60: 5d 20 3d 20 28 76 29 3e 3e 38 2c 20 28 70 29 5b ] = (v)>>8, (p)[
6a70: 31 5d 20 3d 20 28 76 29 29 0a 23 64 65 66 69 6e 1] = (v)).#defin
6a80: 65 20 67 65 74 34 62 79 74 65 20 73 71 6c 69 74 e get4byte sqlit
6a90: 65 33 47 65 74 34 62 79 74 65 0a 23 64 65 66 69 e3Get4byte.#defi
6aa0: 6e 65 20 70 75 74 34 62 79 74 65 20 73 71 6c 69 ne put4byte sqli
6ab0: 74 65 33 50 75 74 34 62 79 74 65 0a 0a 2f 2a 0a te3Put4byte../*.
6ac0: 2a 2a 20 49 6e 74 65 72 6e 61 6c 20 72 6f 75 74 ** Internal rout
6ad0: 69 6e 65 73 20 74 68 61 74 20 73 68 6f 75 6c 64 ines that should
6ae0: 20 62 65 20 61 63 63 65 73 73 65 64 20 62 79 20 be accessed by
6af0: 74 68 65 20 62 74 72 65 65 20 6c 61 79 65 72 20 the btree layer
6b00: 6f 6e 6c 79 2e 0a 2a 2f 0a 69 6e 74 20 73 71 6c only..*/.int sql
6b10: 69 74 65 33 42 74 72 65 65 47 65 74 50 61 67 65 ite3BtreeGetPage
6b20: 28 42 74 53 68 61 72 65 64 2a 2c 20 50 67 6e 6f (BtShared*, Pgno
6b30: 2c 20 4d 65 6d 50 61 67 65 2a 2a 2c 20 69 6e 74 , MemPage**, int
6b40: 29 3b 0a 69 6e 74 20 73 71 6c 69 74 65 33 42 74 );.int sqlite3Bt
6b50: 72 65 65 49 6e 69 74 50 61 67 65 28 4d 65 6d 50 reeInitPage(MemP
6b60: 61 67 65 20 2a 70 50 61 67 65 2c 20 4d 65 6d 50 age *pPage, MemP
6b70: 61 67 65 20 2a 70 50 61 72 65 6e 74 29 3b 0a 76 age *pParent);.v
6b80: 6f 69 64 20 73 71 6c 69 74 65 33 42 74 72 65 65 oid sqlite3Btree
6b90: 50 61 72 73 65 43 65 6c 6c 50 74 72 28 4d 65 6d ParseCellPtr(Mem
6ba0: 50 61 67 65 2a 2c 20 75 38 2a 2c 20 43 65 6c 6c Page*, u8*, Cell
6bb0: 49 6e 66 6f 2a 29 3b 0a 76 6f 69 64 20 73 71 6c Info*);.void sql
6bc0: 69 74 65 33 42 74 72 65 65 50 61 72 73 65 43 65 ite3BtreeParseCe
6bd0: 6c 6c 28 4d 65 6d 50 61 67 65 2a 2c 20 69 6e 74 ll(MemPage*, int
6be0: 2c 20 43 65 6c 6c 49 6e 66 6f 2a 29 3b 0a 23 69 , CellInfo*);.#i
6bf0: 66 64 65 66 20 53 51 4c 49 54 45 5f 54 45 53 54 fdef SQLITE_TEST
6c00: 0a 75 38 20 2a 73 71 6c 69 74 65 33 42 74 72 65 .u8 *sqlite3Btre
6c10: 65 46 69 6e 64 43 65 6c 6c 28 4d 65 6d 50 61 67 eFindCell(MemPag
6c20: 65 20 2a 70 50 61 67 65 2c 20 69 6e 74 20 69 43 e *pPage, int iC
6c30: 65 6c 6c 29 3b 0a 23 65 6e 64 69 66 0a 69 6e 74 ell);.#endif.int
6c40: 20 73 71 6c 69 74 65 33 42 74 72 65 65 52 65 73 sqlite3BtreeRes
6c50: 74 6f 72 65 4f 72 43 6c 65 61 72 43 75 72 73 6f toreOrClearCurso
6c60: 72 50 6f 73 69 74 69 6f 6e 28 42 74 43 75 72 73 rPosition(BtCurs
6c70: 6f 72 20 2a 70 43 75 72 29 3b 0a 76 6f 69 64 20 or *pCur);.void
6c80: 73 71 6c 69 74 65 33 42 74 72 65 65 47 65 74 54 sqlite3BtreeGetT
6c90: 65 6d 70 43 75 72 73 6f 72 28 42 74 43 75 72 73 empCursor(BtCurs
6ca0: 6f 72 20 2a 70 43 75 72 2c 20 42 74 43 75 72 73 or *pCur, BtCurs
6cb0: 6f 72 20 2a 70 54 65 6d 70 43 75 72 29 3b 0a 76 or *pTempCur);.v
6cc0: 6f 69 64 20 73 71 6c 69 74 65 33 42 74 72 65 65 oid sqlite3Btree
6cd0: 52 65 6c 65 61 73 65 54 65 6d 70 43 75 72 73 6f ReleaseTempCurso
6ce0: 72 28 42 74 43 75 72 73 6f 72 20 2a 70 43 75 72 r(BtCursor *pCur
6cf0: 29 3b 0a 69 6e 74 20 73 71 6c 69 74 65 33 42 74 );.int sqlite3Bt
6d00: 72 65 65 49 73 52 6f 6f 74 50 61 67 65 28 4d 65 reeIsRootPage(Me
6d10: 6d 50 61 67 65 20 2a 70 50 61 67 65 29 3b 0a 76 mPage *pPage);.v
6d20: 6f 69 64 20 73 71 6c 69 74 65 33 42 74 72 65 65 oid sqlite3Btree
6d30: 4d 6f 76 65 54 6f 50 61 72 65 6e 74 28 42 74 43 MoveToParent(BtC
6d40: 75 72 73 6f 72 20 2a 70 43 75 72 29 3b 0a ursor *pCur);.