blob: dc702efc0ae794005bdd20de440ed1ae5304c741 [file] [log] [blame]
drha3152892007-05-05 11:48:52 +00001/*
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*************************************************************************
danielk19771ceedd32008-11-19 10:22:33 +000012** $Id: btreeInt.h,v 1.36 2008/11/19 10:22:33 danielk1977 Exp $
drha3152892007-05-05 11:48:52 +000013**
14** This file implements a external (disk-based) database using BTrees.
15** For a detailed discussion of BTrees, refer to
16**
17** Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
18** "Sorting And Searching", pages 473-480. Addison-Wesley
19** Publishing Company, Reading, Massachusetts.
20**
21** The basic idea is that each page of the file contains N database
22** entries and N+1 pointers to subpages.
23**
24** ----------------------------------------------------------------
25** | Ptr(0) | Key(0) | Ptr(1) | Key(1) | ... | Key(N-1) | Ptr(N) |
26** ----------------------------------------------------------------
27**
28** All of the keys on the page that Ptr(0) points to have values less
29** than Key(0). All of the keys on page Ptr(1) and its subpages have
30** values greater than Key(0) and less than Key(1). All of the keys
31** on Ptr(N) and its subpages have values greater than Key(N-1). And
32** so forth.
33**
34** Finding a particular key requires reading O(log(M)) pages from the
35** disk where M is the number of entries in the tree.
36**
37** In this implementation, a single file can hold one or more separate
38** BTrees. Each BTree is identified by the index of its root page. The
39** key and data for any entry are combined to form the "payload". A
40** fixed amount of payload can be carried directly on the database
41** page. If the payload is larger than the preset amount then surplus
42** bytes are stored on overflow pages. The payload for an entry
43** and the preceding pointer are combined to form a "Cell". Each
44** page has a small header which contains the Ptr(N) pointer and other
45** information such as the size of key and data.
46**
47** FORMAT DETAILS
48**
49** The file is divided into pages. The first page is called page 1,
50** the second is page 2, and so forth. A page number of zero indicates
51** "no such page". The page size can be anything between 512 and 65536.
52** Each page can be either a btree page, a freelist page or an overflow
53** page.
54**
55** The first page is always a btree page. The first 100 bytes of the first
56** page contain a special header (the "file header") that describes the file.
57** The format of the file header is as follows:
58**
59** OFFSET SIZE DESCRIPTION
60** 0 16 Header string: "SQLite format 3\000"
61** 16 2 Page size in bytes.
62** 18 1 File format write version
63** 19 1 File format read version
64** 20 1 Bytes of unused space at the end of each page
65** 21 1 Max embedded payload fraction
66** 22 1 Min embedded payload fraction
67** 23 1 Min leaf payload fraction
68** 24 4 File change counter
69** 28 4 Reserved for future use
70** 32 4 First freelist page
71** 36 4 Number of freelist pages in the file
72** 40 60 15 4-byte meta values passed to higher layers
73**
74** All of the integer values are big-endian (most significant byte first).
75**
drh80308692007-06-15 12:06:58 +000076** The file change counter is incremented when the database is changed
77** This counter allows other processes to know when the file has changed
78** and thus when they need to flush their cache.
drha3152892007-05-05 11:48:52 +000079**
80** The max embedded payload fraction is the amount of the total usable
81** space in a page that can be consumed by a single cell for standard
82** B-tree (non-LEAFDATA) tables. A value of 255 means 100%. The default
83** is to limit the maximum cell size so that at least 4 cells will fit
84** on one page. Thus the default max embedded payload fraction is 64.
85**
86** If the payload for a cell is larger than the max payload, then extra
87** payload is spilled to overflow pages. Once an overflow page is allocated,
88** as many bytes as possible are moved into the overflow pages without letting
89** the cell size drop below the min embedded payload fraction.
90**
91** The min leaf payload fraction is like the min embedded payload fraction
92** except that it applies to leaf nodes in a LEAFDATA tree. The maximum
93** payload fraction for a LEAFDATA tree is always 100% (or 255) and it
94** not specified in the header.
95**
96** Each btree pages is divided into three sections: The header, the
drh80308692007-06-15 12:06:58 +000097** cell pointer array, and the cell content area. Page 1 also has a 100-byte
drha3152892007-05-05 11:48:52 +000098** file header that occurs before the page header.
99**
100** |----------------|
101** | file header | 100 bytes. Page 1 only.
102** |----------------|
103** | page header | 8 bytes for leaves. 12 bytes for interior nodes
104** |----------------|
105** | cell pointer | | 2 bytes per cell. Sorted order.
106** | array | | Grows downward
107** | | v
108** |----------------|
109** | unallocated |
110** | space |
111** |----------------| ^ Grows upwards
112** | cell content | | Arbitrary order interspersed with freeblocks.
113** | area | | and free space fragments.
114** |----------------|
115**
116** The page headers looks like this:
117**
118** OFFSET SIZE DESCRIPTION
119** 0 1 Flags. 1: intkey, 2: zerodata, 4: leafdata, 8: leaf
120** 1 2 byte offset to the first freeblock
121** 3 2 number of cells on this page
122** 5 2 first byte of the cell content area
123** 7 1 number of fragmented free bytes
124** 8 4 Right child (the Ptr(N) value). Omitted on leaves.
125**
126** The flags define the format of this btree page. The leaf flag means that
127** this page has no children. The zerodata flag means that this page carries
128** only keys and no data. The intkey flag means that the key is a integer
129** which is stored in the key size entry of the cell header rather than in
130** the payload area.
131**
132** The cell pointer array begins on the first byte after the page header.
133** The cell pointer array contains zero or more 2-byte numbers which are
134** offsets from the beginning of the page to the cell content in the cell
135** content area. The cell pointers occur in sorted order. The system strives
136** to keep free space after the last cell pointer so that new cells can
137** be easily added without having to defragment the page.
138**
139** Cell content is stored at the very end of the page and grows toward the
140** beginning of the page.
141**
142** Unused space within the cell content area is collected into a linked list of
143** freeblocks. Each freeblock is at least 4 bytes in size. The byte offset
144** to the first freeblock is given in the header. Freeblocks occur in
145** increasing order. Because a freeblock must be at least 4 bytes in size,
146** any group of 3 or fewer unused bytes in the cell content area cannot
147** exist on the freeblock chain. A group of 3 or fewer free bytes is called
148** a fragment. The total number of bytes in all fragments is recorded.
149** in the page header at offset 7.
150**
151** SIZE DESCRIPTION
152** 2 Byte offset of the next freeblock
153** 2 Bytes in this freeblock
154**
155** Cells are of variable length. Cells are stored in the cell content area at
156** the end of the page. Pointers to the cells are in the cell pointer array
157** that immediately follows the page header. Cells is not necessarily
158** contiguous or in order, but cell pointers are contiguous and in order.
159**
160** Cell content makes use of variable length integers. A variable
161** length integer is 1 to 9 bytes where the lower 7 bits of each
162** byte are used. The integer consists of all bytes that have bit 8 set and
163** the first byte with bit 8 clear. The most significant byte of the integer
164** appears first. A variable-length integer may not be more than 9 bytes long.
165** As a special case, all 8 bytes of the 9th byte are used as data. This
166** allows a 64-bit integer to be encoded in 9 bytes.
167**
168** 0x00 becomes 0x00000000
169** 0x7f becomes 0x0000007f
170** 0x81 0x00 becomes 0x00000080
171** 0x82 0x00 becomes 0x00000100
172** 0x80 0x7f becomes 0x0000007f
173** 0x8a 0x91 0xd1 0xac 0x78 becomes 0x12345678
174** 0x81 0x81 0x81 0x81 0x01 becomes 0x10204081
175**
176** Variable length integers are used for rowids and to hold the number of
177** bytes of key and data in a btree cell.
178**
179** The content of a cell looks like this:
180**
181** SIZE DESCRIPTION
182** 4 Page number of the left child. Omitted if leaf flag is set.
183** var Number of bytes of data. Omitted if the zerodata flag is set.
184** var Number of bytes of key. Or the key itself if intkey flag is set.
185** * Payload
186** 4 First page of the overflow chain. Omitted if no overflow
187**
188** Overflow pages form a linked list. Each page except the last is completely
189** filled with data (pagesize - 4 bytes). The last page can have as little
190** as 1 byte of data.
191**
192** SIZE DESCRIPTION
193** 4 Page number of next overflow page
194** * Data
195**
196** Freelist pages come in two subtypes: trunk pages and leaf pages. The
drh80308692007-06-15 12:06:58 +0000197** file header points to the first in a linked list of trunk page. Each trunk
drha3152892007-05-05 11:48:52 +0000198** page points to multiple leaf pages. The content of a leaf page is
199** unspecified. A trunk page looks like this:
200**
201** SIZE DESCRIPTION
202** 4 Page number of next trunk page
203** 4 Number of leaf pointers on this page
204** * zero or more pages numbers of leaves
205*/
206#include "sqliteInt.h"
207#include "pager.h"
208#include "btree.h"
209#include "os.h"
210#include <assert.h>
211
212/* Round up a number to the next larger multiple of 8. This is used
213** to force 8-byte alignment on 64-bit architectures.
214*/
215#define ROUND8(x) ((x+7)&~7)
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) (pBt->pageSize-8)
222
223/* The maximum number of cells on a single page of the database. This
drha9121e42008-02-19 14:59:35 +0000224** 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.
drha3152892007-05-05 11:48:52 +0000227*/
drha9121e42008-02-19 14:59:35 +0000228#define MX_CELL(pBt) ((pBt->pageSize-8)/6)
drha3152892007-05-05 11:48:52 +0000229
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
drhe53831d2007-08-17 01:14:38 +0000252** first byte of on-disk image of every BTree page.
drha3152892007-05-05 11:48:52 +0000253*/
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.
drhd677b3d2007-08-20 22:48:41 +0000268**
269** Access to all fields of this structure is controlled by the mutex
270** stored in MemPage.pBt->mutex.
drha3152892007-05-05 11:48:52 +0000271*/
272struct MemPage {
273 u8 isInit; /* True if previously initialized. MUST BE FIRST! */
drha3152892007-05-05 11:48:52 +0000274 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 */
drha3152892007-05-05 11:48:52 +0000277 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 */
drhe53831d2007-08-17 01:14:38 +0000280 u16 maxLocal; /* Copy of BtShared.maxLocal or BtShared.maxLeaf */
281 u16 minLocal; /* Copy of BtShared.minLocal or BtShared.minLeaf */
drha3152892007-05-05 11:48:52 +0000282 u16 cellOffset; /* Index in aData of first cell pointer */
drha3152892007-05-05 11:48:52 +0000283 u16 nFree; /* Number of free bytes on the page */
284 u16 nCell; /* Number of cells on this page, local and ovfl */
drh1688c862008-07-18 02:44:17 +0000285 u16 maskPage; /* Mask for page offset */
drha3152892007-05-05 11:48:52 +0000286 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];
drhe53831d2007-08-17 01:14:38 +0000290 BtShared *pBt; /* Pointer to BtShared that this page is part of */
291 u8 *aData; /* Pointer to disk image of the page data */
drha3152892007-05-05 11:48:52 +0000292 DbPage *pDbPage; /* Pager page handle */
293 Pgno pgno; /* Page number for this page */
drha3152892007-05-05 11:48:52 +0000294};
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
drhe53831d2007-08-17 01:14:38 +0000303/* A Btree handle
304**
305** A database connection contains a pointer to an instance of
306** this object for every database file that it has open. This structure
307** is opaque to the database connection. The database connection cannot
308** see the internals of this structure and only deals with pointers to
309** this structure.
310**
311** For some database files, the same underlying database cache might be
312** shared between multiple connections. In that case, each contection
313** has it own pointer to this object. But each instance of this object
314** points to the same BtShared object. The database cache and the
315** schema associated with the database file are all contained within
316** the BtShared object.
drhabddb0c2007-08-20 13:14:28 +0000317**
drhd0679ed2007-08-28 22:24:34 +0000318** All fields in this structure are accessed under sqlite3.mutex.
319** The pBt pointer itself may not be changed while there exists cursors
320** in the referenced BtShared that point back to this Btree since those
321** cursors have to do go through this Btree to find their BtShared and
322** they often do so without holding sqlite3.mutex.
drhe53831d2007-08-17 01:14:38 +0000323*/
drha3152892007-05-05 11:48:52 +0000324struct Btree {
drhe5fe6902007-12-07 18:55:28 +0000325 sqlite3 *db; /* The database connection holding this btree */
drhe53831d2007-08-17 01:14:38 +0000326 BtShared *pBt; /* Sharable content of this btree */
327 u8 inTrans; /* TRANS_NONE, TRANS_READ or TRANS_WRITE */
drhe5fe6902007-12-07 18:55:28 +0000328 u8 sharable; /* True if we can share pBt with another db */
329 u8 locked; /* True if db currently has pBt locked */
drhe53831d2007-08-17 01:14:38 +0000330 int wantToLock; /* Number of nested calls to sqlite3BtreeEnter() */
drhe5fe6902007-12-07 18:55:28 +0000331 Btree *pNext; /* List of other sharable Btrees from the same db */
drhe53831d2007-08-17 01:14:38 +0000332 Btree *pPrev; /* Back pointer of the same list */
drha3152892007-05-05 11:48:52 +0000333};
334
335/*
336** Btree.inTrans may take one of the following values.
337**
338** If the shared-data extension is enabled, there may be multiple users
339** of the Btree structure. At most one of these may open a write transaction,
drhe53831d2007-08-17 01:14:38 +0000340** but any number may have active read transactions.
drha3152892007-05-05 11:48:52 +0000341*/
342#define TRANS_NONE 0
343#define TRANS_READ 1
344#define TRANS_WRITE 2
345
346/*
drhe53831d2007-08-17 01:14:38 +0000347** An instance of this object represents a single database file.
348**
349** A single database file can be in use as the same time by two
350** or more database connections. When two or more connections are
351** sharing the same database file, each connection has it own
352** private Btree object for the file and each of those Btrees points
353** to this one BtShared object. BtShared.nRef is the number of
354** connections currently sharing this database file.
drhabddb0c2007-08-20 13:14:28 +0000355**
356** Fields in this structure are accessed under the BtShared.mutex
357** mutex, except for nRef and pNext which are accessed under the
drhb1ab8ea2007-08-29 00:33:07 +0000358** global SQLITE_MUTEX_STATIC_MASTER mutex. The pPager field
359** may not be modified once it is initially set as long as nRef>0.
360** The pSchema field may be set once under BtShared.mutex and
361** thereafter is unchanged as long as nRef>0.
drha3152892007-05-05 11:48:52 +0000362*/
363struct BtShared {
364 Pager *pPager; /* The page cache */
drhe5fe6902007-12-07 18:55:28 +0000365 sqlite3 *db; /* Database connection currently using this Btree */
drha3152892007-05-05 11:48:52 +0000366 BtCursor *pCursor; /* A list of all open cursors */
367 MemPage *pPage1; /* First page of the database */
368 u8 inStmt; /* True if we are in a statement subtransaction */
369 u8 readOnly; /* True if the underlying file is readonly */
drha3152892007-05-05 11:48:52 +0000370 u8 pageSizeFixed; /* True if the page size can no longer be changed */
371#ifndef SQLITE_OMIT_AUTOVACUUM
372 u8 autoVacuum; /* True if auto-vacuum is enabled */
373 u8 incrVacuum; /* True if incr-vacuum is enabled */
374 Pgno nTrunc; /* Non-zero if the db will be truncated (incr vacuum) */
375#endif
376 u16 pageSize; /* Total number of bytes on a page */
377 u16 usableSize; /* Number of usable bytes on each page */
378 int maxLocal; /* Maximum local payload in non-LEAFDATA tables */
379 int minLocal; /* Minimum local payload in non-LEAFDATA tables */
380 int maxLeaf; /* Maximum local payload in a LEAFDATA table */
381 int minLeaf; /* Minimum local payload in a LEAFDATA table */
drha3152892007-05-05 11:48:52 +0000382 u8 inTransaction; /* Transaction state */
drha3152892007-05-05 11:48:52 +0000383 int nTransaction; /* Number of open transactions (read + write) */
384 void *pSchema; /* Pointer to space allocated by sqlite3BtreeSchema() */
385 void (*xFreeSchema)(void*); /* Destructor for BtShared.pSchema */
drh86f8c192007-08-22 00:39:19 +0000386 sqlite3_mutex *mutex; /* Non-recursive mutex required to access this struct */
drha3152892007-05-05 11:48:52 +0000387#ifndef SQLITE_OMIT_SHARED_CACHE
drhabddb0c2007-08-20 13:14:28 +0000388 int nRef; /* Number of references to this structure */
389 BtShared *pNext; /* Next on a list of sharable BtShared structs */
drha3152892007-05-05 11:48:52 +0000390 BtLock *pLock; /* List of locks held on this shared-btree struct */
danielk1977641b0f42007-12-21 04:47:25 +0000391 Btree *pExclusive; /* Btree with an EXCLUSIVE lock on the whole db */
drha3152892007-05-05 11:48:52 +0000392#endif
danielk197752ae7242008-03-25 14:24:56 +0000393 u8 *pTmpSpace; /* BtShared.pageSize bytes of space for tmp use */
drha3152892007-05-05 11:48:52 +0000394};
395
396/*
397** An instance of the following structure is used to hold information
398** about a cell. The parseCellPtr() function fills in this structure
399** based on information extract from the raw disk page.
400*/
401typedef struct CellInfo CellInfo;
402struct CellInfo {
403 u8 *pCell; /* Pointer to the start of cell content */
404 i64 nKey; /* The key for INTKEY tables, or number of bytes in key */
405 u32 nData; /* Number of bytes of data */
406 u32 nPayload; /* Total amount of payload */
407 u16 nHeader; /* Size of the cell content header in bytes */
408 u16 nLocal; /* Amount of payload held locally */
409 u16 iOverflow; /* Offset to overflow page number. Zero if no overflow */
410 u16 nSize; /* Size of the cell content on the main b-tree page */
411};
412
413/*
danielk197771d5d2c2008-09-29 11:49:47 +0000414** Maximum depth of an SQLite B-Tree structure. Any B-Tree deeper than
415** this will be declared corrupt. This value is calculated based on a
416** maximum database size of 2^31 pages a minimum fanout of 2 for a
417** root-node and 3 for all other internal nodes.
418**
419** If a tree that appears to be taller than this is encountered, it is
420** assumed that the database is corrupt.
421*/
422#define BTCURSOR_MAX_DEPTH 20
423
424/*
drhe53831d2007-08-17 01:14:38 +0000425** A cursor is a pointer to a particular entry within a particular
426** b-tree within a database file.
427**
drha3152892007-05-05 11:48:52 +0000428** The entry is identified by its MemPage and the index in
429** MemPage.aCell[] of the entry.
drhe53831d2007-08-17 01:14:38 +0000430**
431** When a single database file can shared by two more database connections,
432** but cursors cannot be shared. Each cursor is associated with a
drhe5fe6902007-12-07 18:55:28 +0000433** particular database connection identified BtCursor.pBtree.db.
drhabddb0c2007-08-20 13:14:28 +0000434**
drhd677b3d2007-08-20 22:48:41 +0000435** Fields in this structure are accessed under the BtShared.mutex
drhd0679ed2007-08-28 22:24:34 +0000436** found at self->pBt->mutex.
drha3152892007-05-05 11:48:52 +0000437*/
438struct BtCursor {
439 Btree *pBtree; /* The Btree to which this cursor belongs */
drhd0679ed2007-08-28 22:24:34 +0000440 BtShared *pBt; /* The BtShared this cursor points to */
drha3152892007-05-05 11:48:52 +0000441 BtCursor *pNext, *pPrev; /* Forms a linked list of all cursors */
drh1e968a02008-03-25 00:22:21 +0000442 struct KeyInfo *pKeyInfo; /* Argument passed to comparison function */
drha3152892007-05-05 11:48:52 +0000443 Pgno pgnoRoot; /* The root page of this tree */
drha3152892007-05-05 11:48:52 +0000444 CellInfo info; /* A parse of the cell we are pointing at */
445 u8 wrFlag; /* True if writable */
drha2c20e42008-03-29 16:01:04 +0000446 u8 atLast; /* Cursor pointing to the last entry */
447 u8 validNKey; /* True if info.nKey is valid */
drha3152892007-05-05 11:48:52 +0000448 u8 eState; /* One of the CURSOR_XXX constants (see below) */
449 void *pKey; /* Saved key that was cursor's last known position */
450 i64 nKey; /* Size of pKey, or last integer key */
451 int skip; /* (skip<0) -> Prev() is a no-op. (skip>0) -> Next() is */
452#ifndef SQLITE_OMIT_INCRBLOB
453 u8 isIncrblobHandle; /* True if this cursor is an incr. io handle */
454 Pgno *aOverflow; /* Cache of overflow page locations */
455#endif
drhf94a1732008-09-30 17:18:17 +0000456#ifndef NDEBUG
457 u8 pagesShuffled; /* True if Btree pages are rearranged by balance()*/
458#endif
danielk197771d5d2c2008-09-29 11:49:47 +0000459 i16 iPage; /* Index of current page in apPage */
460 MemPage *apPage[BTCURSOR_MAX_DEPTH]; /* Pages from root to current page */
461 u16 aiIdx[BTCURSOR_MAX_DEPTH]; /* Current index in apPage[i] */
drha3152892007-05-05 11:48:52 +0000462};
463
464/*
465** Potential values for BtCursor.eState.
466**
467** CURSOR_VALID:
468** Cursor points to a valid entry. getPayload() etc. may be called.
469**
470** CURSOR_INVALID:
471** Cursor does not point to a valid entry. This can happen (for example)
472** because the table is empty or because BtreeCursorFirst() has not been
473** called.
474**
475** CURSOR_REQUIRESEEK:
476** The table that this cursor was opened on still exists, but has been
477** modified since the cursor was last used. The cursor position is saved
478** in variables BtCursor.pKey and BtCursor.nKey. When a cursor is in
drha3460582008-07-11 21:02:53 +0000479** this state, restoreCursorPosition() can be called to attempt to
drha3152892007-05-05 11:48:52 +0000480** seek the cursor to the saved position.
drhfb982642007-08-30 01:19:59 +0000481**
482** CURSOR_FAULT:
483** A unrecoverable error (an I/O error or a malloc failure) has occurred
484** on a different connection that shares the BtShared cache with this
485** cursor. The error has left the cache in an inconsistent state.
486** Do nothing else with this cursor. Any attempt to use the cursor
487** should return the error code stored in BtCursor.skip
drha3152892007-05-05 11:48:52 +0000488*/
489#define CURSOR_INVALID 0
490#define CURSOR_VALID 1
491#define CURSOR_REQUIRESEEK 2
drhfb982642007-08-30 01:19:59 +0000492#define CURSOR_FAULT 3
drha3152892007-05-05 11:48:52 +0000493
drha3152892007-05-05 11:48:52 +0000494/* The database page the PENDING_BYTE occupies. This page is never used.
495** TODO: This macro is very similary to PAGER_MJ_PGNO() in pager.c. They
496** should possibly be consolidated (presumably in pager.h).
497**
498** If disk I/O is omitted (meaning that the database is stored purely
499** in memory) then there is no pending byte.
500*/
501#ifdef SQLITE_OMIT_DISKIO
502# define PENDING_BYTE_PAGE(pBt) 0x7fffffff
503#else
danielk197789d40042008-11-17 14:20:56 +0000504# define PENDING_BYTE_PAGE(pBt) ((Pgno)((PENDING_BYTE/(pBt)->pageSize)+1))
drha3152892007-05-05 11:48:52 +0000505#endif
506
507/*
508** A linked list of the following structures is stored at BtShared.pLock.
509** Locks are added (or upgraded from READ_LOCK to WRITE_LOCK) when a cursor
510** is opened on the table with root page BtShared.iTable. Locks are removed
511** from this list when a transaction is committed or rolled back, or when
512** a btree handle is closed.
513*/
514struct BtLock {
515 Btree *pBtree; /* Btree handle holding this lock */
516 Pgno iTable; /* Root page of table */
517 u8 eLock; /* READ_LOCK or WRITE_LOCK */
518 BtLock *pNext; /* Next in BtShared.pLock list */
519};
520
521/* Candidate values for BtLock.eLock */
522#define READ_LOCK 1
523#define WRITE_LOCK 2
524
525/*
526** These macros define the location of the pointer-map entry for a
527** database page. The first argument to each is the number of usable
528** bytes on each page of the database (often 1024). The second is the
529** page number to look up in the pointer map.
530**
531** PTRMAP_PAGENO returns the database page number of the pointer-map
532** page that stores the required pointer. PTRMAP_PTROFFSET returns
533** the offset of the requested map entry.
534**
535** If the pgno argument passed to PTRMAP_PAGENO is a pointer-map page,
536** then pgno is returned. So (pgno==PTRMAP_PAGENO(pgsz, pgno)) can be
537** used to test if pgno is a pointer-map page. PTRMAP_ISPAGE implements
538** this test.
539*/
540#define PTRMAP_PAGENO(pBt, pgno) ptrmapPageno(pBt, pgno)
danielk19778c666b12008-07-18 09:34:57 +0000541#define PTRMAP_PTROFFSET(pgptrmap, pgno) (5*(pgno-pgptrmap-1))
drha3152892007-05-05 11:48:52 +0000542#define PTRMAP_ISPAGE(pBt, pgno) (PTRMAP_PAGENO((pBt),(pgno))==(pgno))
543
544/*
545** The pointer map is a lookup table that identifies the parent page for
546** each child page in the database file. The parent page is the page that
547** contains a pointer to the child. Every page in the database contains
548** 0 or 1 parent pages. (In this context 'database page' refers
549** to any page that is not part of the pointer map itself.) Each pointer map
550** entry consists of a single byte 'type' and a 4 byte parent page number.
551** The PTRMAP_XXX identifiers below are the valid types.
552**
553** The purpose of the pointer map is to facility moving pages from one
554** position in the file to another as part of autovacuum. When a page
555** is moved, the pointer in its parent must be updated to point to the
556** new location. The pointer map is used to locate the parent page quickly.
557**
558** PTRMAP_ROOTPAGE: The database page is a root-page. The page-number is not
559** used in this case.
560**
561** PTRMAP_FREEPAGE: The database page is an unused (free) page. The page-number
562** is not used in this case.
563**
564** PTRMAP_OVERFLOW1: The database page is the first page in a list of
565** overflow pages. The page number identifies the page that
566** contains the cell with a pointer to this overflow page.
567**
568** PTRMAP_OVERFLOW2: The database page is the second or later page in a list of
569** overflow pages. The page-number identifies the previous
570** page in the overflow page list.
571**
572** PTRMAP_BTREE: The database page is a non-root btree page. The page number
573** identifies the parent page in the btree.
574*/
575#define PTRMAP_ROOTPAGE 1
576#define PTRMAP_FREEPAGE 2
577#define PTRMAP_OVERFLOW1 3
578#define PTRMAP_OVERFLOW2 4
579#define PTRMAP_BTREE 5
580
581/* A bunch of assert() statements to check the transaction state variables
582** of handle p (type Btree*) are internally consistent.
583*/
584#define btreeIntegrity(p) \
drha3152892007-05-05 11:48:52 +0000585 assert( p->pBt->inTransaction!=TRANS_NONE || p->pBt->nTransaction==0 ); \
586 assert( p->pBt->inTransaction>=p->inTrans );
587
588
589/*
590** The ISAUTOVACUUM macro is used within balance_nonroot() to determine
591** if the database supports auto-vacuum or not. Because it is used
592** within an expression that is an argument to another macro
593** (sqliteMallocRaw), it is not possible to use conditional compilation.
594** So, this macro is defined instead.
595*/
596#ifndef SQLITE_OMIT_AUTOVACUUM
597#define ISAUTOVACUUM (pBt->autoVacuum)
598#else
599#define ISAUTOVACUUM 0
600#endif
601
602
603/*
604** This structure is passed around through all the sanity checking routines
605** in order to keep track of some global state information.
606*/
607typedef struct IntegrityCk IntegrityCk;
608struct IntegrityCk {
609 BtShared *pBt; /* The tree being checked out */
610 Pager *pPager; /* The associated pager. Also accessible by pBt->pPager */
danielk197789d40042008-11-17 14:20:56 +0000611 Pgno nPage; /* Number of pages in the database */
drha3152892007-05-05 11:48:52 +0000612 int *anRef; /* Number of times each page is referenced */
613 int mxErr; /* Stop accumulating errors when this reaches zero */
drha3152892007-05-05 11:48:52 +0000614 int nErr; /* Number of messages written to zErrMsg so far */
drhc890fec2008-08-01 20:10:08 +0000615 int mallocFailed; /* A memory allocation error has occurred */
drhf089aa42008-07-08 19:34:06 +0000616 StrAccum errMsg; /* Accumulate the error message text here */
drha3152892007-05-05 11:48:52 +0000617};
618
619/*
620** Read or write a two- and four-byte big-endian integer values.
621*/
danielk19771cc5ed82007-05-16 17:28:43 +0000622#define get2byte(x) ((x)[0]<<8 | (x)[1])
623#define put2byte(p,v) ((p)[0] = (v)>>8, (p)[1] = (v))
drha3152892007-05-05 11:48:52 +0000624#define get4byte sqlite3Get4byte
drha3152892007-05-05 11:48:52 +0000625#define put4byte sqlite3Put4byte
drh16a9b832007-05-05 18:39:25 +0000626
627/*
628** Internal routines that should be accessed by the btree layer only.
629*/
630int sqlite3BtreeGetPage(BtShared*, Pgno, MemPage**, int);
danielk197771d5d2c2008-09-29 11:49:47 +0000631int sqlite3BtreeInitPage(MemPage *pPage);
drh16a9b832007-05-05 18:39:25 +0000632void sqlite3BtreeParseCellPtr(MemPage*, u8*, CellInfo*);
633void sqlite3BtreeParseCell(MemPage*, int, CellInfo*);
drha3460582008-07-11 21:02:53 +0000634int sqlite3BtreeRestoreCursorPosition(BtCursor *pCur);
drh16a9b832007-05-05 18:39:25 +0000635void sqlite3BtreeGetTempCursor(BtCursor *pCur, BtCursor *pTempCur);
636void sqlite3BtreeReleaseTempCursor(BtCursor *pCur);
drh16a9b832007-05-05 18:39:25 +0000637void sqlite3BtreeMoveToParent(BtCursor *pCur);