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