1/*
2** 2004 April 6
3**
4** The author disclaims copyright to this source code.  In place of
5** a legal notice, here is a blessing:
6**
7**    May you do good and not evil.
8**    May you find forgiveness for yourself and forgive others.
9**    May you share freely, never taking more than you give.
10**
11*************************************************************************
12** This file implements a external (disk-based) database using BTrees.
13** For a detailed discussion of BTrees, refer to
14**
15**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
16**     "Sorting And Searching", pages 473-480. Addison-Wesley
17**     Publishing Company, Reading, Massachusetts.
18**
19** The basic idea is that each page of the file contains N database
20** entries and N+1 pointers to subpages.
21**
22**   ----------------------------------------------------------------
23**   |  Ptr(0) | Key(0) | Ptr(1) | Key(1) | ... | Key(N-1) | Ptr(N) |
24**   ----------------------------------------------------------------
25**
26** All of the keys on the page that Ptr(0) points to have values less
27** than Key(0).  All of the keys on page Ptr(1) and its subpages have
28** values greater than Key(0) and less than Key(1).  All of the keys
29** on Ptr(N) and its subpages have values greater than Key(N-1).  And
30** so forth.
31**
32** Finding a particular key requires reading O(log(M)) pages from the
33** disk where M is the number of entries in the tree.
34**
35** In this implementation, a single file can hold one or more separate
36** BTrees.  Each BTree is identified by the index of its root page.  The
37** key and data for any entry are combined to form the "payload".  A
38** fixed amount of payload can be carried directly on the database
39** page.  If the payload is larger than the preset amount then surplus
40** bytes are stored on overflow pages.  The payload for an entry
41** and the preceding pointer are combined to form a "Cell".  Each
42** page has a small header which contains the Ptr(N) pointer and other
43** information such as the size of key and data.
44**
45** FORMAT DETAILS
46**
47** The file is divided into pages.  The first page is called page 1,
48** the second is page 2, and so forth.  A page number of zero indicates
49** "no such page".  The page size can be any power of 2 between 512 and 65536.
50** Each page can be either a btree page, a freelist page, an overflow
51** page, or a pointer-map page.
52**
53** The first page is always a btree page.  The first 100 bytes of the first
54** page contain a special header (the "file header") that describes the file.
55** The format of the file header is as follows:
56**
57**   OFFSET   SIZE    DESCRIPTION
58**      0      16     Header string: "SQLite format 3\000"
59**     16       2     Page size in bytes.
60**     18       1     File format write version
61**     19       1     File format read version
62**     20       1     Bytes of unused space at the end of each page
63**     21       1     Max embedded payload fraction
64**     22       1     Min embedded payload fraction
65**     23       1     Min leaf payload fraction
66**     24       4     File change counter
67**     28       4     Reserved for future use
68**     32       4     First freelist page
69**     36       4     Number of freelist pages in the file
70**     40      60     15 4-byte meta values passed to higher layers
71**
72**     40       4     Schema cookie
73**     44       4     File format of schema layer
74**     48       4     Size of page cache
75**     52       4     Largest root-page (auto/incr_vacuum)
76**     56       4     1=UTF-8 2=UTF16le 3=UTF16be
77**     60       4     User version
78**     64       4     Incremental vacuum mode
79**     68       4     unused
80**     72       4     unused
81**     76       4     unused
82**
83** All of the integer values are big-endian (most significant byte first).
84**
85** The file change counter is incremented when the database is changed
86** This counter allows other processes to know when the file has changed
87** and thus when they need to flush their cache.
88**
89** The max embedded payload fraction is the amount of the total usable
90** space in a page that can be consumed by a single cell for standard
91** B-tree (non-LEAFDATA) tables.  A value of 255 means 100%.  The default
92** is to limit the maximum cell size so that at least 4 cells will fit
93** on one page.  Thus the default max embedded payload fraction is 64.
94**
95** If the payload for a cell is larger than the max payload, then extra
96** payload is spilled to overflow pages.  Once an overflow page is allocated,
97** as many bytes as possible are moved into the overflow pages without letting
98** the cell size drop below the min embedded payload fraction.
99**
100** The min leaf payload fraction is like the min embedded payload fraction
101** except that it applies to leaf nodes in a LEAFDATA tree.  The maximum
102** payload fraction for a LEAFDATA tree is always 100% (or 255) and it
103** not specified in the header.
104**
105** Each btree pages is divided into three sections:  The header, the
106** cell pointer array, and the cell content area.  Page 1 also has a 100-byte
107** file header that occurs before the page header.
108**
109**      |----------------|
110**      | file header    |   100 bytes.  Page 1 only.
111**      |----------------|
112**      | page header    |   8 bytes for leaves.  12 bytes for interior nodes
113**      |----------------|
114**      | cell pointer   |   |  2 bytes per cell.  Sorted order.
115**      | array          |   |  Grows downward
116**      |                |   v
117**      |----------------|
118**      | unallocated    |
119**      | space          |
120**      |----------------|   ^  Grows upwards
121**      | cell content   |   |  Arbitrary order interspersed with freeblocks.
122**      | area           |   |  and free space fragments.
123**      |----------------|
124**
125** The page headers looks like this:
126**
127**   OFFSET   SIZE     DESCRIPTION
128**      0       1      Flags. 1: intkey, 2: zerodata, 4: leafdata, 8: leaf
129**      1       2      byte offset to the first freeblock
130**      3       2      number of cells on this page
131**      5       2      first byte of the cell content area
132**      7       1      number of fragmented free bytes
133**      8       4      Right child (the Ptr(N) value).  Omitted on leaves.
134**
135** The flags define the format of this btree page.  The leaf flag means that
136** this page has no children.  The zerodata flag means that this page carries
137** only keys and no data.  The intkey flag means that the key is a integer
138** which is stored in the key size entry of the cell header rather than in
139** the payload area.
140**
141** The cell pointer array begins on the first byte after the page header.
142** The cell pointer array contains zero or more 2-byte numbers which are
143** offsets from the beginning of the page to the cell content in the cell
144** content area.  The cell pointers occur in sorted order.  The system strives
145** to keep free space after the last cell pointer so that new cells can
146** be easily added without having to defragment the page.
147**
148** Cell content is stored at the very end of the page and grows toward the
149** beginning of the page.
150**
151** Unused space within the cell content area is collected into a linked list of
152** freeblocks.  Each freeblock is at least 4 bytes in size.  The byte offset
153** to the first freeblock is given in the header.  Freeblocks occur in
154** increasing order.  Because a freeblock must be at least 4 bytes in size,
155** any group of 3 or fewer unused bytes in the cell content area cannot
156** exist on the freeblock chain.  A group of 3 or fewer free bytes is called
157** a fragment.  The total number of bytes in all fragments is recorded.
158** in the page header at offset 7.
159**
160**    SIZE    DESCRIPTION
161**      2     Byte offset of the next freeblock
162**      2     Bytes in this freeblock
163**
164** Cells are of variable length.  Cells are stored in the cell content area at
165** the end of the page.  Pointers to the cells are in the cell pointer array
166** that immediately follows the page header.  Cells is not necessarily
167** contiguous or in order, but cell pointers are contiguous and in order.
168**
169** Cell content makes use of variable length integers.  A variable
170** length integer is 1 to 9 bytes where the lower 7 bits of each
171** byte are used.  The integer consists of all bytes that have bit 8 set and
172** the first byte with bit 8 clear.  The most significant byte of the integer
173** appears first.  A variable-length integer may not be more than 9 bytes long.
174** As a special case, all 8 bytes of the 9th byte are used as data.  This
175** allows a 64-bit integer to be encoded in 9 bytes.
176**
177**    0x00                      becomes  0x00000000
178**    0x7f                      becomes  0x0000007f
179**    0x81 0x00                 becomes  0x00000080
180**    0x82 0x00                 becomes  0x00000100
181**    0x80 0x7f                 becomes  0x0000007f
182**    0x8a 0x91 0xd1 0xac 0x78  becomes  0x12345678
183**    0x81 0x81 0x81 0x81 0x01  becomes  0x10204081
184**
185** Variable length integers are used for rowids and to hold the number of
186** bytes of key and data in a btree cell.
187**
188** The content of a cell looks like this:
189**
190**    SIZE    DESCRIPTION
191**      4     Page number of the left child. Omitted if leaf flag is set.
192**     var    Number of bytes of data. Omitted if the zerodata flag is set.
193**     var    Number of bytes of key. Or the key itself if intkey flag is set.
194**      *     Payload
195**      4     First page of the overflow chain.  Omitted if no overflow
196**
197** Overflow pages form a linked list.  Each page except the last is completely
198** filled with data (pagesize - 4 bytes).  The last page can have as little
199** as 1 byte of data.
200**
201**    SIZE    DESCRIPTION
202**      4     Page number of next overflow page
203**      *     Data
204**
205** Freelist pages come in two subtypes: trunk pages and leaf pages.  The
206** file header points to the first in a linked list of trunk page.  Each trunk
207** page points to multiple leaf pages.  The content of a leaf page is
208** unspecified.  A trunk page looks like this:
209**
210**    SIZE    DESCRIPTION
211**      4     Page number of next trunk page
212**      4     Number of leaf pointers on this page
213**      *     zero or more pages numbers of leaves
214*/
215#include "sqliteInt.h"
216
217
218/* The following value is the maximum cell size assuming a maximum page
219** size give above.
220*/
221#define MX_CELL_SIZE(pBt)  ((int)(pBt->pageSize-8))
222
223/* The maximum number of cells on a single page of the database.  This
224** assumes a minimum cell size of 6 bytes  (4 bytes for the cell itself
225** plus 2 bytes for the index to the cell in the page header).  Such
226** small cells will be rare, but they are possible.
227*/
228#define MX_CELL(pBt) ((pBt->pageSize-8)/6)
229
230/* Forward declarations */
231typedef struct MemPage MemPage;
232typedef struct BtLock BtLock;
233
234/*
235** This is a magic string that appears at the beginning of every
236** SQLite database in order to identify the file as a real database.
237**
238** You can change this value at compile-time by specifying a
239** -DSQLITE_FILE_HEADER="..." on the compiler command-line.  The
240** header must be exactly 16 bytes including the zero-terminator so
241** the string itself should be 15 characters long.  If you change
242** the header, then your custom library will not be able to read
243** databases generated by the standard tools and the standard tools
244** will not be able to read databases created by your custom library.
245*/
246#ifndef SQLITE_FILE_HEADER /* 123456789 123456 */
247#  define SQLITE_FILE_HEADER "SQLite format 3"
248#endif
249
250/*
251** Page type flags.  An ORed combination of these flags appear as the
252** first byte of on-disk image of every BTree page.
253*/
254#define PTF_INTKEY    0x01
255#define PTF_ZERODATA  0x02
256#define PTF_LEAFDATA  0x04
257#define PTF_LEAF      0x08
258
259/*
260** As each page of the file is loaded into memory, an instance of the following
261** structure is appended and initialized to zero.  This structure stores
262** information about the page that is decoded from the raw file page.
263**
264** The pParent field points back to the parent page.  This allows us to
265** walk up the BTree from any leaf to the root.  Care must be taken to
266** unref() the parent page pointer when this page is no longer referenced.
267** The pageDestructor() routine handles that chore.
268**
269** Access to all fields of this structure is controlled by the mutex
270** stored in MemPage.pBt->mutex.
271*/
272struct MemPage {
273  u8 isInit;           /* True if previously initialized. MUST BE FIRST! */
274  u8 nOverflow;        /* Number of overflow cell bodies in aCell[] */
275  u8 intKey;           /* True if intkey flag is set */
276  u8 leaf;             /* True if leaf flag is set */
277  u8 hasData;          /* True if this page stores data */
278  u8 hdrOffset;        /* 100 for page 1.  0 otherwise */
279  u8 childPtrSize;     /* 0 if leaf==1.  4 if leaf==0 */
280  u16 maxLocal;        /* Copy of BtShared.maxLocal or BtShared.maxLeaf */
281  u16 minLocal;        /* Copy of BtShared.minLocal or BtShared.minLeaf */
282  u16 cellOffset;      /* Index in aData of first cell pointer */
283  u16 nFree;           /* Number of free bytes on the page */
284  u16 nCell;           /* Number of cells on this page, local and ovfl */
285  u16 maskPage;        /* Mask for page offset */
286  struct _OvflCell {   /* Cells that will not fit on aData[] */
287    u8 *pCell;          /* Pointers to the body of the overflow cell */
288    u16 idx;            /* Insert this cell before idx-th non-overflow cell */
289  } aOvfl[5];
290  BtShared *pBt;       /* Pointer to BtShared that this page is part of */
291  u8 *aData;           /* Pointer to disk image of the page data */
292  DbPage *pDbPage;     /* Pager page handle */
293  Pgno pgno;           /* Page number for this page */
294};
295
296/*
297** The in-memory image of a disk page has the auxiliary information appended
298** to the end.  EXTRA_SIZE is the number of bytes of space needed to hold
299** that extra information.
300*/
301#define EXTRA_SIZE sizeof(MemPage)
302
303/*
304** A linked list of the following structures is stored at BtShared.pLock.
305** Locks are added (or upgraded from READ_LOCK to WRITE_LOCK) when a cursor
306** is opened on the table with root page BtShared.iTable. Locks are removed
307** from this list when a transaction is committed or rolled back, or when
308** a btree handle is closed.
309*/
310struct BtLock {
311  Btree *pBtree;        /* Btree handle holding this lock */
312  Pgno iTable;          /* Root page of table */
313  u8 eLock;             /* READ_LOCK or WRITE_LOCK */
314  BtLock *pNext;        /* Next in BtShared.pLock list */
315};
316
317/* Candidate values for BtLock.eLock */
318#define READ_LOCK     1
319#define WRITE_LOCK    2
320
321/* A Btree handle
322**
323** A database connection contains a pointer to an instance of
324** this object for every database file that it has open.  This structure
325** is opaque to the database connection.  The database connection cannot
326** see the internals of this structure and only deals with pointers to
327** this structure.
328**
329** For some database files, the same underlying database cache might be
330** shared between multiple connections.  In that case, each connection
331** has it own instance of this object.  But each instance of this object
332** points to the same BtShared object.  The database cache and the
333** schema associated with the database file are all contained within
334** the BtShared object.
335**
336** All fields in this structure are accessed under sqlite3.mutex.
337** The pBt pointer itself may not be changed while there exists cursors
338** in the referenced BtShared that point back to this Btree since those
339** cursors have to go through this Btree to find their BtShared and
340** they often do so without holding sqlite3.mutex.
341*/
342struct Btree {
343  sqlite3 *db;       /* The database connection holding this btree */
344  BtShared *pBt;     /* Sharable content of this btree */
345  u8 inTrans;        /* TRANS_NONE, TRANS_READ or TRANS_WRITE */
346  u8 sharable;       /* True if we can share pBt with another db */
347  u8 locked;         /* True if db currently has pBt locked */
348  int wantToLock;    /* Number of nested calls to sqlite3BtreeEnter() */
349  int nBackup;       /* Number of backup operations reading this btree */
350  Btree *pNext;      /* List of other sharable Btrees from the same db */
351  Btree *pPrev;      /* Back pointer of the same list */
352#ifndef SQLITE_OMIT_SHARED_CACHE
353  BtLock lock;       /* Object used to lock page 1 */
354#endif
355};
356
357/*
358** Btree.inTrans may take one of the following values.
359**
360** If the shared-data extension is enabled, there may be multiple users
361** of the Btree structure. At most one of these may open a write transaction,
362** but any number may have active read transactions.
363*/
364#define TRANS_NONE  0
365#define TRANS_READ  1
366#define TRANS_WRITE 2
367
368/*
369** An instance of this object represents a single database file.
370**
371** A single database file can be in use as the same time by two
372** or more database connections.  When two or more connections are
373** sharing the same database file, each connection has it own
374** private Btree object for the file and each of those Btrees points
375** to this one BtShared object.  BtShared.nRef is the number of
376** connections currently sharing this database file.
377**
378** Fields in this structure are accessed under the BtShared.mutex
379** mutex, except for nRef and pNext which are accessed under the
380** global SQLITE_MUTEX_STATIC_MASTER mutex.  The pPager field
381** may not be modified once it is initially set as long as nRef>0.
382** The pSchema field may be set once under BtShared.mutex and
383** thereafter is unchanged as long as nRef>0.
384**
385** isPending:
386**
387**   If a BtShared client fails to obtain a write-lock on a database
388**   table (because there exists one or more read-locks on the table),
389**   the shared-cache enters 'pending-lock' state and isPending is
390**   set to true.
391**
392**   The shared-cache leaves the 'pending lock' state when either of
393**   the following occur:
394**
395**     1) The current writer (BtShared.pWriter) concludes its transaction, OR
396**     2) The number of locks held by other connections drops to zero.
397**
398**   while in the 'pending-lock' state, no connection may start a new
399**   transaction.
400**
401**   This feature is included to help prevent writer-starvation.
402*/
403struct BtShared {
404  Pager *pPager;        /* The page cache */
405  sqlite3 *db;          /* Database connection currently using this Btree */
406  BtCursor *pCursor;    /* A list of all open cursors */
407  MemPage *pPage1;      /* First page of the database */
408  u8 readOnly;          /* True if the underlying file is readonly */
409  u8 pageSizeFixed;     /* True if the page size can no longer be changed */
410  u8 secureDelete;      /* True if secure_delete is enabled */
411  u8 initiallyEmpty;    /* Database is empty at start of transaction */
412  u8 openFlags;         /* Flags to sqlite3BtreeOpen() */
413#ifndef SQLITE_OMIT_AUTOVACUUM
414  u8 autoVacuum;        /* True if auto-vacuum is enabled */
415  u8 incrVacuum;        /* True if incr-vacuum is enabled */
416#endif
417  u8 inTransaction;     /* Transaction state */
418  u8 doNotUseWAL;       /* If true, do not open write-ahead-log file */
419  u16 maxLocal;         /* Maximum local payload in non-LEAFDATA tables */
420  u16 minLocal;         /* Minimum local payload in non-LEAFDATA tables */
421  u16 maxLeaf;          /* Maximum local payload in a LEAFDATA table */
422  u16 minLeaf;          /* Minimum local payload in a LEAFDATA table */
423  u32 pageSize;         /* Total number of bytes on a page */
424  u32 usableSize;       /* Number of usable bytes on each page */
425  int nTransaction;     /* Number of open transactions (read + write) */
426  u32 nPage;            /* Number of pages in the database */
427  void *pSchema;        /* Pointer to space allocated by sqlite3BtreeSchema() */
428  void (*xFreeSchema)(void*);  /* Destructor for BtShared.pSchema */
429  sqlite3_mutex *mutex; /* Non-recursive mutex required to access this object */
430  Bitvec *pHasContent;  /* Set of pages moved to free-list this transaction */
431#ifndef SQLITE_OMIT_SHARED_CACHE
432  int nRef;             /* Number of references to this structure */
433  BtShared *pNext;      /* Next on a list of sharable BtShared structs */
434  BtLock *pLock;        /* List of locks held on this shared-btree struct */
435  Btree *pWriter;       /* Btree with currently open write transaction */
436  u8 isExclusive;       /* True if pWriter has an EXCLUSIVE lock on the db */
437  u8 isPending;         /* If waiting for read-locks to clear */
438#endif
439  u8 *pTmpSpace;        /* BtShared.pageSize bytes of space for tmp use */
440};
441
442/*
443** An instance of the following structure is used to hold information
444** about a cell.  The parseCellPtr() function fills in this structure
445** based on information extract from the raw disk page.
446*/
447typedef struct CellInfo CellInfo;
448struct CellInfo {
449  i64 nKey;      /* The key for INTKEY tables, or number of bytes in key */
450  u8 *pCell;     /* Pointer to the start of cell content */
451  u32 nData;     /* Number of bytes of data */
452  u32 nPayload;  /* Total amount of payload */
453  u16 nHeader;   /* Size of the cell content header in bytes */
454  u16 nLocal;    /* Amount of payload held locally */
455  u16 iOverflow; /* Offset to overflow page number.  Zero if no overflow */
456  u16 nSize;     /* Size of the cell content on the main b-tree page */
457};
458
459/*
460** Maximum depth of an SQLite B-Tree structure. Any B-Tree deeper than
461** this will be declared corrupt. This value is calculated based on a
462** maximum database size of 2^31 pages a minimum fanout of 2 for a
463** root-node and 3 for all other internal nodes.
464**
465** If a tree that appears to be taller than this is encountered, it is
466** assumed that the database is corrupt.
467*/
468#define BTCURSOR_MAX_DEPTH 20
469
470/*
471** A cursor is a pointer to a particular entry within a particular
472** b-tree within a database file.
473**
474** The entry is identified by its MemPage and the index in
475** MemPage.aCell[] of the entry.
476**
477** A single database file can shared by two more database connections,
478** but cursors cannot be shared.  Each cursor is associated with a
479** particular database connection identified BtCursor.pBtree.db.
480**
481** Fields in this structure are accessed under the BtShared.mutex
482** found at self->pBt->mutex.
483*/
484struct BtCursor {
485  Btree *pBtree;            /* The Btree to which this cursor belongs */
486  BtShared *pBt;            /* The BtShared this cursor points to */
487  BtCursor *pNext, *pPrev;  /* Forms a linked list of all cursors */
488  struct KeyInfo *pKeyInfo; /* Argument passed to comparison function */
489  Pgno pgnoRoot;            /* The root page of this tree */
490  sqlite3_int64 cachedRowid; /* Next rowid cache.  0 means not valid */
491  CellInfo info;            /* A parse of the cell we are pointing at */
492  i64 nKey;        /* Size of pKey, or last integer key */
493  void *pKey;      /* Saved key that was cursor's last known position */
494  int skipNext;    /* Prev() is noop if negative. Next() is noop if positive */
495  u8 wrFlag;                /* True if writable */
496  u8 atLast;                /* Cursor pointing to the last entry */
497  u8 validNKey;             /* True if info.nKey is valid */
498  u8 eState;                /* One of the CURSOR_XXX constants (see below) */
499#ifndef SQLITE_OMIT_INCRBLOB
500  Pgno *aOverflow;          /* Cache of overflow page locations */
501  u8 isIncrblobHandle;      /* True if this cursor is an incr. io handle */
502#endif
503  i16 iPage;                            /* Index of current page in apPage */
504  u16 aiIdx[BTCURSOR_MAX_DEPTH];        /* Current index in apPage[i] */
505  MemPage *apPage[BTCURSOR_MAX_DEPTH];  /* Pages from root to current page */
506};
507
508/*
509** Potential values for BtCursor.eState.
510**
511** CURSOR_VALID:
512**   Cursor points to a valid entry. getPayload() etc. may be called.
513**
514** CURSOR_INVALID:
515**   Cursor does not point to a valid entry. This can happen (for example)
516**   because the table is empty or because BtreeCursorFirst() has not been
517**   called.
518**
519** CURSOR_REQUIRESEEK:
520**   The table that this cursor was opened on still exists, but has been
521**   modified since the cursor was last used. The cursor position is saved
522**   in variables BtCursor.pKey and BtCursor.nKey. When a cursor is in
523**   this state, restoreCursorPosition() can be called to attempt to
524**   seek the cursor to the saved position.
525**
526** CURSOR_FAULT:
527**   A unrecoverable error (an I/O error or a malloc failure) has occurred
528**   on a different connection that shares the BtShared cache with this
529**   cursor.  The error has left the cache in an inconsistent state.
530**   Do nothing else with this cursor.  Any attempt to use the cursor
531**   should return the error code stored in BtCursor.skip
532*/
533#define CURSOR_INVALID           0
534#define CURSOR_VALID             1
535#define CURSOR_REQUIRESEEK       2
536#define CURSOR_FAULT             3
537
538/*
539** The database page the PENDING_BYTE occupies. This page is never used.
540*/
541# define PENDING_BYTE_PAGE(pBt) PAGER_MJ_PGNO(pBt)
542
543/*
544** These macros define the location of the pointer-map entry for a
545** database page. The first argument to each is the number of usable
546** bytes on each page of the database (often 1024). The second is the
547** page number to look up in the pointer map.
548**
549** PTRMAP_PAGENO returns the database page number of the pointer-map
550** page that stores the required pointer. PTRMAP_PTROFFSET returns
551** the offset of the requested map entry.
552**
553** If the pgno argument passed to PTRMAP_PAGENO is a pointer-map page,
554** then pgno is returned. So (pgno==PTRMAP_PAGENO(pgsz, pgno)) can be
555** used to test if pgno is a pointer-map page. PTRMAP_ISPAGE implements
556** this test.
557*/
558#define PTRMAP_PAGENO(pBt, pgno) ptrmapPageno(pBt, pgno)
559#define PTRMAP_PTROFFSET(pgptrmap, pgno) (5*(pgno-pgptrmap-1))
560#define PTRMAP_ISPAGE(pBt, pgno) (PTRMAP_PAGENO((pBt),(pgno))==(pgno))
561
562/*
563** The pointer map is a lookup table that identifies the parent page for
564** each child page in the database file.  The parent page is the page that
565** contains a pointer to the child.  Every page in the database contains
566** 0 or 1 parent pages.  (In this context 'database page' refers
567** to any page that is not part of the pointer map itself.)  Each pointer map
568** entry consists of a single byte 'type' and a 4 byte parent page number.
569** The PTRMAP_XXX identifiers below are the valid types.
570**
571** The purpose of the pointer map is to facility moving pages from one
572** position in the file to another as part of autovacuum.  When a page
573** is moved, the pointer in its parent must be updated to point to the
574** new location.  The pointer map is used to locate the parent page quickly.
575**
576** PTRMAP_ROOTPAGE: The database page is a root-page. The page-number is not
577**                  used in this case.
578**
579** PTRMAP_FREEPAGE: The database page is an unused (free) page. The page-number
580**                  is not used in this case.
581**
582** PTRMAP_OVERFLOW1: The database page is the first page in a list of
583**                   overflow pages. The page number identifies the page that
584**                   contains the cell with a pointer to this overflow page.
585**
586** PTRMAP_OVERFLOW2: The database page is the second or later page in a list of
587**                   overflow pages. The page-number identifies the previous
588**                   page in the overflow page list.
589**
590** PTRMAP_BTREE: The database page is a non-root btree page. The page number
591**               identifies the parent page in the btree.
592*/
593#define PTRMAP_ROOTPAGE 1
594#define PTRMAP_FREEPAGE 2
595#define PTRMAP_OVERFLOW1 3
596#define PTRMAP_OVERFLOW2 4
597#define PTRMAP_BTREE 5
598
599/* A bunch of assert() statements to check the transaction state variables
600** of handle p (type Btree*) are internally consistent.
601*/
602#define btreeIntegrity(p) \
603  assert( p->pBt->inTransaction!=TRANS_NONE || p->pBt->nTransaction==0 ); \
604  assert( p->pBt->inTransaction>=p->inTrans );
605
606
607/*
608** The ISAUTOVACUUM macro is used within balance_nonroot() to determine
609** if the database supports auto-vacuum or not. Because it is used
610** within an expression that is an argument to another macro
611** (sqliteMallocRaw), it is not possible to use conditional compilation.
612** So, this macro is defined instead.
613*/
614#ifndef SQLITE_OMIT_AUTOVACUUM
615#define ISAUTOVACUUM (pBt->autoVacuum)
616#else
617#define ISAUTOVACUUM 0
618#endif
619
620
621/*
622** This structure is passed around through all the sanity checking routines
623** in order to keep track of some global state information.
624*/
625typedef struct IntegrityCk IntegrityCk;
626struct IntegrityCk {
627  BtShared *pBt;    /* The tree being checked out */
628  Pager *pPager;    /* The associated pager.  Also accessible by pBt->pPager */
629  Pgno nPage;       /* Number of pages in the database */
630  int *anRef;       /* Number of times each page is referenced */
631  int mxErr;        /* Stop accumulating errors when this reaches zero */
632  int nErr;         /* Number of messages written to zErrMsg so far */
633  int mallocFailed; /* A memory allocation error has occurred */
634  StrAccum errMsg;  /* Accumulate the error message text here */
635};
636
637/*
638** Read or write a two- and four-byte big-endian integer values.
639*/
640#define get2byte(x)   ((x)[0]<<8 | (x)[1])
641#define put2byte(p,v) ((p)[0] = (u8)((v)>>8), (p)[1] = (u8)(v))
642#define get4byte sqlite3Get4byte
643#define put4byte sqlite3Put4byte
644