1 /*

     2 ** 2004 April 6

     3 **

     4 ** The author disclaims copyright to this source code.  In place of

     5 ** a legal notice, here is a blessing:

     6 **

     7 **    May you do good and not evil.

     8 **    May you find forgiveness for yourself and forgive others.

     9 **    May you share freely, never taking more than you give.

    10 **

    11 *************************************************************************

    12 ** $Id: btree.c,v 1.328 2006/08/16 16:42:48 drh Exp $

    13 **

    14 ** This file implements a external (disk-based) database using BTrees.

    15 ** For a detailed discussion of BTrees, refer to

    16 **

    17 **     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:

    18 **     "Sorting And Searching", pages 473-480. Addison-Wesley

    19 **     Publishing Company, Reading, Massachusetts.

    20 **

    21 ** The basic idea is that each page of the file contains N database

    22 ** entries and N+1 pointers to subpages.

    23 **

    24 **   ----------------------------------------------------------------

    25 **   |  Ptr(0) | Key(0) | Ptr(1) | Key(1) | ... | Key(N) | Ptr(N+1) |

    26 **   ----------------------------------------------------------------

    27 **

    28 ** All of the keys on the page that Ptr(0) points to have values less

    29 ** than Key(0).  All of the keys on page Ptr(1) and its subpages have

    30 ** values greater than Key(0) and less than Key(1).  All of the keys

    31 ** on Ptr(N+1) and its subpages have values greater than Key(N).  And

    32 ** so forth.

    33 **

    34 ** Finding a particular key requires reading O(log(M)) pages from the 

    35 ** disk where M is the number of entries in the tree.

    36 **

    37 ** In this implementation, a single file can hold one or more separate 

    38 ** BTrees.  Each BTree is identified by the index of its root page.  The

    39 ** key and data for any entry are combined to form the "payload".  A

    40 ** fixed amount of payload can be carried directly on the database

    41 ** page.  If the payload is larger than the preset amount then surplus

    42 ** bytes are stored on overflow pages.  The payload for an entry

    43 ** and the preceding pointer are combined to form a "Cell".  Each 

    44 ** page has a small header which contains the Ptr(N+1) pointer and other

    45 ** information such as the size of key and data.

    46 **

    47 ** FORMAT DETAILS

    48 **

    49 ** The file is divided into pages.  The first page is called page 1,

    50 ** the second is page 2, and so forth.  A page number of zero indicates

    51 ** "no such page".  The page size can be anything between 512 and 65536.

    52 ** Each page can be either a btree page, a freelist page or an overflow

    53 ** page.

    54 **

    55 ** The first page is always a btree page.  The first 100 bytes of the first

    56 ** page contain a special header (the "file header") that describes the file.

    57 ** The format of the file header is as follows:

    58 **

    59 **   OFFSET   SIZE    DESCRIPTION

    60 **      0      16     Header string: "SQLite format 3\000"

    61 **     16       2     Page size in bytes.  

    62 **     18       1     File format write version

    63 **     19       1     File format read version

    64 **     20       1     Bytes of unused space at the end of each page

    65 **     21       1     Max embedded payload fraction

    66 **     22       1     Min embedded payload fraction

    67 **     23       1     Min leaf payload fraction

    68 **     24       4     File change counter

    69 **     28       4     Reserved for future use

    70 **     32       4     First freelist page

    71 **     36       4     Number of freelist pages in the file

    72 **     40      60     15 4-byte meta values passed to higher layers

    73 **

    74 ** All of the integer values are big-endian (most significant byte first).

    75 **

    76 ** The file change counter is incremented when the database is changed more

    77 ** than once within the same second.  This counter, together with the

    78 ** modification time of the file, allows other processes to know

    79 ** when the file has changed and thus when they need to flush their

    80 ** cache.

    81 **

    82 ** The max embedded payload fraction is the amount of the total usable

    83 ** space in a page that can be consumed by a single cell for standard

    84 ** B-tree (non-LEAFDATA) tables.  A value of 255 means 100%.  The default

    85 ** is to limit the maximum cell size so that at least 4 cells will fit

    86 ** on one page.  Thus the default max embedded payload fraction is 64.

    87 **

    88 ** If the payload for a cell is larger than the max payload, then extra

    89 ** payload is spilled to overflow pages.  Once an overflow page is allocated,

    90 ** as many bytes as possible are moved into the overflow pages without letting

    91 ** the cell size drop below the min embedded payload fraction.

    92 **

    93 ** The min leaf payload fraction is like the min embedded payload fraction

    94 ** except that it applies to leaf nodes in a LEAFDATA tree.  The maximum

    95 ** payload fraction for a LEAFDATA tree is always 100% (or 255) and it

    96 ** not specified in the header.

    97 **

    98 ** Each btree pages is divided into three sections:  The header, the

    99 ** cell pointer array, and the cell area area.  Page 1 also has a 100-byte

   100 ** file header that occurs before the page header.

   101 **

   102 **      |----------------|

   103 **      | file header    |   100 bytes.  Page 1 only.

   104 **      |----------------|

   105 **      | page header    |   8 bytes for leaves.  12 bytes for interior nodes

   106 **      |----------------|

   107 **      | cell pointer   |   |  2 bytes per cell.  Sorted order.

   108 **      | array          |   |  Grows downward

   109 **      |                |   v

   110 **      |----------------|

   111 **      | unallocated    |

   112 **      | space          |

   113 **      |----------------|   ^  Grows upwards

   114 **      | cell content   |   |  Arbitrary order interspersed with freeblocks.

   115 **      | area           |   |  and free space fragments.

   116 **      |----------------|

   117 **

   118 ** The page headers looks like this:

   119 **

   120 **   OFFSET   SIZE     DESCRIPTION

   121 **      0       1      Flags. 1: intkey, 2: zerodata, 4: leafdata, 8: leaf

   122 **      1       2      byte offset to the first freeblock

   123 **      3       2      number of cells on this page

   124 **      5       2      first byte of the cell content area

   125 **      7       1      number of fragmented free bytes

   126 **      8       4      Right child (the Ptr(N+1) value).  Omitted on leaves.

   127 **

   128 ** The flags define the format of this btree page.  The leaf flag means that

   129 ** this page has no children.  The zerodata flag means that this page carries

   130 ** only keys and no data.  The intkey flag means that the key is a integer

   131 ** which is stored in the key size entry of the cell header rather than in

   132 ** the payload area.

   133 **

   134 ** The cell pointer array begins on the first byte after the page header.

   135 ** The cell pointer array contains zero or more 2-byte numbers which are

   136 ** offsets from the beginning of the page to the cell content in the cell

   137 ** content area.  The cell pointers occur in sorted order.  The system strives

   138 ** to keep free space after the last cell pointer so that new cells can

   139 ** be easily added without having to defragment the page.

   140 **

   141 ** Cell content is stored at the very end of the page and grows toward the

   142 ** beginning of the page.

   143 **

   144 ** Unused space within the cell content area is collected into a linked list of

   145 ** freeblocks.  Each freeblock is at least 4 bytes in size.  The byte offset

   146 ** to the first freeblock is given in the header.  Freeblocks occur in

   147 ** increasing order.  Because a freeblock must be at least 4 bytes in size,

   148 ** any group of 3 or fewer unused bytes in the cell content area cannot

   149 ** exist on the freeblock chain.  A group of 3 or fewer free bytes is called

   150 ** a fragment.  The total number of bytes in all fragments is recorded.

   151 ** in the page header at offset 7.

   152 **

   153 **    SIZE    DESCRIPTION

   154 **      2     Byte offset of the next freeblock

   155 **      2     Bytes in this freeblock

   156 **

   157 ** Cells are of variable length.  Cells are stored in the cell content area at

   158 ** the end of the page.  Pointers to the cells are in the cell pointer array

   159 ** that immediately follows the page header.  Cells is not necessarily

   160 ** contiguous or in order, but cell pointers are contiguous and in order.

   161 **

   162 ** Cell content makes use of variable length integers.  A variable

   163 ** length integer is 1 to 9 bytes where the lower 7 bits of each 

   164 ** byte are used.  The integer consists of all bytes that have bit 8 set and

   165 ** the first byte with bit 8 clear.  The most significant byte of the integer

   166 ** appears first.  A variable-length integer may not be more than 9 bytes long.

   167 ** As a special case, all 8 bytes of the 9th byte are used as data.  This

   168 ** allows a 64-bit integer to be encoded in 9 bytes.

   169 **

   170 **    0x00                      becomes  0x00000000

   171 **    0x7f                      becomes  0x0000007f

   172 **    0x81 0x00                 becomes  0x00000080

   173 **    0x82 0x00                 becomes  0x00000100

   174 **    0x80 0x7f                 becomes  0x0000007f

   175 **    0x8a 0x91 0xd1 0xac 0x78  becomes  0x12345678

   176 **    0x81 0x81 0x81 0x81 0x01  becomes  0x10204081

   177 **

   178 ** Variable length integers are used for rowids and to hold the number of

   179 ** bytes of key and data in a btree cell.

   180 **

   181 ** The content of a cell looks like this:

   182 **

   183 **    SIZE    DESCRIPTION

   184 **      4     Page number of the left child. Omitted if leaf flag is set.

   185 **     var    Number of bytes of data. Omitted if the zerodata flag is set.

   186 **     var    Number of bytes of key. Or the key itself if intkey flag is set.

   187 **      *     Payload

   188 **      4     First page of the overflow chain.  Omitted if no overflow

   189 **

   190 ** Overflow pages form a linked list.  Each page except the last is completely

   191 ** filled with data (pagesize - 4 bytes).  The last page can have as little

   192 ** as 1 byte of data.

   193 **

   194 **    SIZE    DESCRIPTION

   195 **      4     Page number of next overflow page

   196 **      *     Data

   197 **

   198 ** Freelist pages come in two subtypes: trunk pages and leaf pages.  The

   199 ** file header points to first in a linked list of trunk page.  Each trunk

   200 ** page points to multiple leaf pages.  The content of a leaf page is

   201 ** unspecified.  A trunk page looks like this:

   202 **

   203 **    SIZE    DESCRIPTION

   204 **      4     Page number of next trunk page

   205 **      4     Number of leaf pointers on this page

   206 **      *     zero or more pages numbers of leaves

   207 */

   208 #include "sqliteInt.h"

   209 #include "pager.h"

   210 #include "btree.h"

   211 #include "os.h"

   212 #include <assert.h>

   213 

   214 /* Round up a number to the next larger multiple of 8.  This is used

   215 ** to force 8-byte alignment on 64-bit architectures.

   216 */

   217 #define ROUND8(x)   ((x+7)&~7)

   218 

   219 

   220 /* The following value is the maximum cell size assuming a maximum page

   221 ** size give above.

   222 */

   223 #define MX_CELL_SIZE(pBt)  (pBt->pageSize-8)

   224 

   225 /* The maximum number of cells on a single page of the database.  This

   226 ** assumes a minimum cell size of 3 bytes.  Such small cells will be

   227 ** exceedingly rare, but they are possible.

   228 */

   229 #define MX_CELL(pBt) ((pBt->pageSize-8)/3)

   230 

   231 /* Forward declarations */

   232 typedef struct MemPage MemPage;

   233 typedef struct BtLock BtLock;

   234 

   235 /*

   236 ** This is a magic string that appears at the beginning of every

   237 ** SQLite database in order to identify the file as a real database.

   238 **

   239 ** You can change this value at compile-time by specifying a

   240 ** -DSQLITE_FILE_HEADER="..." on the compiler command-line.  The

   241 ** header must be exactly 16 bytes including the zero-terminator so

   242 ** the string itself should be 15 characters long.  If you change

   243 ** the header, then your custom library will not be able to read 

   244 ** databases generated by the standard tools and the standard tools

   245 ** will not be able to read databases created by your custom library.

   246 */

   247 #ifndef SQLITE_FILE_HEADER /* 123456789 123456 */

   248 #  define SQLITE_FILE_HEADER "SQLite format 3"

   249 #endif

   250 static const char zMagicHeader[] = SQLITE_FILE_HEADER;

   251 

   252 /*

   253 ** Page type flags.  An ORed combination of these flags appear as the

   254 ** first byte of every BTree page.

   255 */

   256 #define PTF_INTKEY    0x01

   257 #define PTF_ZERODATA  0x02

   258 #define PTF_LEAFDATA  0x04

   259 #define PTF_LEAF      0x08

   260 

   261 /*

   262 ** As each page of the file is loaded into memory, an instance of the following

   263 ** structure is appended and initialized to zero.  This structure stores

   264 ** information about the page that is decoded from the raw file page.

   265 **

   266 ** The pParent field points back to the parent page.  This allows us to

   267 ** walk up the BTree from any leaf to the root.  Care must be taken to

   268 ** unref() the parent page pointer when this page is no longer referenced.

   269 ** The pageDestructor() routine handles that chore.

   270 */

   271 struct MemPage {

   272   u8 isInit;           /* True if previously initialized. MUST BE FIRST! */

   273   u8 idxShift;         /* True if Cell indices have changed */

   274   u8 nOverflow;        /* Number of overflow cell bodies in aCell[] */

   275   u8 intKey;           /* True if intkey flag is set */

   276   u8 leaf;             /* True if leaf flag is set */

   277   u8 zeroData;         /* True if table stores keys only */

   278   u8 leafData;         /* True if tables stores data on leaves only */

   279   u8 hasData;          /* True if this page stores data */

   280   u8 hdrOffset;        /* 100 for page 1.  0 otherwise */

   281   u8 childPtrSize;     /* 0 if leaf==1.  4 if leaf==0 */

   282   u16 maxLocal;        /* Copy of Btree.maxLocal or Btree.maxLeaf */

   283   u16 minLocal;        /* Copy of Btree.minLocal or Btree.minLeaf */

   284   u16 cellOffset;      /* Index in aData of first cell pointer */

   285   u16 idxParent;       /* Index in parent of this node */

   286   u16 nFree;           /* Number of free bytes on the page */

   287   u16 nCell;           /* Number of cells on this page, local and ovfl */

   288   struct _OvflCell {   /* Cells that will not fit on aData[] */

   289     u8 *pCell;          /* Pointers to the body of the overflow cell */

   290     u16 idx;            /* Insert this cell before idx-th non-overflow cell */

   291   } aOvfl[5];

   292   BtShared *pBt;       /* Pointer back to BTree structure */

   293   u8 *aData;           /* Pointer back to the start of the page */

   294   Pgno pgno;           /* Page number for this page */

   295   MemPage *pParent;    /* The parent of this page.  NULL for root */

   296 };

   297 

   298 /*

   299 ** The in-memory image of a disk page has the auxiliary information appended

   300 ** to the end.  EXTRA_SIZE is the number of bytes of space needed to hold

   301 ** that extra information.

   302 */

   303 #define EXTRA_SIZE sizeof(MemPage)

   304 

   305 /* Btree handle */

   306 struct Btree {

   307   sqlite3 *pSqlite;

   308   BtShared *pBt;

   309   u8 inTrans;            /* TRANS_NONE, TRANS_READ or TRANS_WRITE */

   310 };

   311 

   312 /*

   313 ** Btree.inTrans may take one of the following values.

   314 **

   315 ** If the shared-data extension is enabled, there may be multiple users

   316 ** of the Btree structure. At most one of these may open a write transaction,

   317 ** but any number may have active read transactions. Variable Btree.pDb 

   318 ** points to the handle that owns any current write-transaction.

   319 */

   320 #define TRANS_NONE  0

   321 #define TRANS_READ  1

   322 #define TRANS_WRITE 2

   323 

   324 /*

   325 ** Everything we need to know about an open database

   326 */

   327 struct BtShared {

   328   Pager *pPager;        /* The page cache */

   329   BtCursor *pCursor;    /* A list of all open cursors */

   330   MemPage *pPage1;      /* First page of the database */

   331   u8 inStmt;            /* True if we are in a statement subtransaction */

   332   u8 readOnly;          /* True if the underlying file is readonly */

   333   u8 maxEmbedFrac;      /* Maximum payload as % of total page size */

   334   u8 minEmbedFrac;      /* Minimum payload as % of total page size */

   335   u8 minLeafFrac;       /* Minimum leaf payload as % of total page size */

   336   u8 pageSizeFixed;     /* True if the page size can no longer be changed */

   337 #ifndef SQLITE_OMIT_AUTOVACUUM

   338   u8 autoVacuum;        /* True if database supports auto-vacuum */

   339 #endif

   340   u16 pageSize;         /* Total number of bytes on a page */

   341   u16 usableSize;       /* Number of usable bytes on each page */

   342   int maxLocal;         /* Maximum local payload in non-LEAFDATA tables */

   343   int minLocal;         /* Minimum local payload in non-LEAFDATA tables */

   344   int maxLeaf;          /* Maximum local payload in a LEAFDATA table */

   345   int minLeaf;          /* Minimum local payload in a LEAFDATA table */

   346   BusyHandler *pBusyHandler;   /* Callback for when there is lock contention */

   347   u8 inTransaction;     /* Transaction state */

   348   int nRef;             /* Number of references to this structure */

   349   int nTransaction;     /* Number of open transactions (read + write) */

   350   void *pSchema;        /* Pointer to space allocated by sqlite3BtreeSchema() */

   351   void (*xFreeSchema)(void*);  /* Destructor for BtShared.pSchema */

   352 #ifndef SQLITE_OMIT_SHARED_CACHE

   353   BtLock *pLock;        /* List of locks held on this shared-btree struct */

   354   BtShared *pNext;      /* Next in ThreadData.pBtree linked list */

   355 #endif

   356 };

   357 

   358 /*

   359 ** An instance of the following structure is used to hold information

   360 ** about a cell.  The parseCellPtr() function fills in this structure

   361 ** based on information extract from the raw disk page.

   362 */

   363 typedef struct CellInfo CellInfo;

   364 struct CellInfo {

   365   u8 *pCell;     /* Pointer to the start of cell content */

   366   i64 nKey;      /* The key for INTKEY tables, or number of bytes in key */

   367   u32 nData;     /* Number of bytes of data */

   368   u16 nHeader;   /* Size of the cell content header in bytes */

   369   u16 nLocal;    /* Amount of payload held locally */

   370   u16 iOverflow; /* Offset to overflow page number.  Zero if no overflow */

   371   u16 nSize;     /* Size of the cell content on the main b-tree page */

   372 };

   373 

   374 /*

   375 ** A cursor is a pointer to a particular entry in the BTree.

   376 ** The entry is identified by its MemPage and the index in

   377 ** MemPage.aCell[] of the entry.

   378 */

   379 struct BtCursor {

   380   Btree *pBtree;            /* The Btree to which this cursor belongs */

   381   BtCursor *pNext, *pPrev;  /* Forms a linked list of all cursors */

   382   int (*xCompare)(void*,int,const void*,int,const void*); /* Key comp func */

   383   void *pArg;               /* First arg to xCompare() */

   384   Pgno pgnoRoot;            /* The root page of this tree */

   385   MemPage *pPage;           /* Page that contains the entry */

   386   int idx;                  /* Index of the entry in pPage->aCell[] */

   387   CellInfo info;            /* A parse of the cell we are pointing at */

   388   u8 wrFlag;                /* True if writable */

   389   u8 eState;                /* One of the CURSOR_XXX constants (see below) */

   390   void *pKey;      /* Saved key that was cursor's last known position */

   391   i64 nKey;        /* Size of pKey, or last integer key */

   392   int skip;        /* (skip<0) -> Prev() is a no-op. (skip>0) -> Next() is */

   393 };

   394 

   395 /*

   396 ** Potential values for BtCursor.eState.

   397 **

   398 ** CURSOR_VALID:

   399 **   Cursor points to a valid entry. getPayload() etc. may be called.

   400 **

   401 ** CURSOR_INVALID:

   402 **   Cursor does not point to a valid entry. This can happen (for example) 

   403 **   because the table is empty or because BtreeCursorFirst() has not been

   404 **   called.

   405 **

   406 ** CURSOR_REQUIRESEEK:

   407 **   The table that this cursor was opened on still exists, but has been 

   408 **   modified since the cursor was last used. The cursor position is saved

   409 **   in variables BtCursor.pKey and BtCursor.nKey. When a cursor is in 

   410 **   this state, restoreOrClearCursorPosition() can be called to attempt to

   411 **   seek the cursor to the saved position.

   412 */

   413 #define CURSOR_INVALID           0

   414 #define CURSOR_VALID             1

   415 #define CURSOR_REQUIRESEEK       2

   416 

   417 /*

   418 ** The TRACE macro will print high-level status information about the

   419 ** btree operation when the global variable sqlite3_btree_trace is

   420 ** enabled.

   421 */

   422 #if SQLITE_TEST

   423 # define TRACE(X)   if( sqlite3_btree_trace )\

   424                         { sqlite3DebugPrintf X; fflush(stdout); }

   425 int sqlite3_btree_trace=0;  /* True to enable tracing */

   426 #else

   427 # define TRACE(X)

   428 #endif

   429 

   430 /*

   431 ** Forward declaration

   432 */

   433 static int checkReadLocks(Btree*,Pgno,BtCursor*);

   434 

   435 /*

   436 ** Read or write a two- and four-byte big-endian integer values.

   437 */

   438 static u32 get2byte(unsigned char *p){

   439   return (p[0]<<8) | p[1];

   440 }

   441 static u32 get4byte(unsigned char *p){

   442   return (p[0]<<24) | (p[1]<<16) | (p[2]<<8) | p[3];

   443 }

   444 static void put2byte(unsigned char *p, u32 v){

   445   p[0] = v>>8;

   446   p[1] = v;

   447 }

   448 static void put4byte(unsigned char *p, u32 v){

   449   p[0] = v>>24;

   450   p[1] = v>>16;

   451   p[2] = v>>8;

   452   p[3] = v;

   453 }

   454 

   455 /*

   456 ** Routines to read and write variable-length integers.  These used to

   457 ** be defined locally, but now we use the varint routines in the util.c

   458 ** file.

   459 */

   460 #define getVarint    sqlite3GetVarint

   461 /* #define getVarint32  sqlite3GetVarint32 */

   462 #define getVarint32(A,B)  ((*B=*(A))<=0x7f?1:sqlite3GetVarint32(A,B))

   463 #define putVarint    sqlite3PutVarint

   464 

   465 /* The database page the PENDING_BYTE occupies. This page is never used.

   466 ** TODO: This macro is very similary to PAGER_MJ_PGNO() in pager.c. They

   467 ** should possibly be consolidated (presumably in pager.h).

   468 **

   469 ** If disk I/O is omitted (meaning that the database is stored purely

   470 ** in memory) then there is no pending byte.

   471 */

   472 #ifdef SQLITE_OMIT_DISKIO

   473 # define PENDING_BYTE_PAGE(pBt)  0x7fffffff

   474 #else

   475 # define PENDING_BYTE_PAGE(pBt) ((PENDING_BYTE/(pBt)->pageSize)+1)

   476 #endif

   477 

   478 /*

   479 ** A linked list of the following structures is stored at BtShared.pLock.

   480 ** Locks are added (or upgraded from READ_LOCK to WRITE_LOCK) when a cursor 

   481 ** is opened on the table with root page BtShared.iTable. Locks are removed

   482 ** from this list when a transaction is committed or rolled back, or when

   483 ** a btree handle is closed.

   484 */

   485 struct BtLock {

   486   Btree *pBtree;        /* Btree handle holding this lock */

   487   Pgno iTable;          /* Root page of table */

   488   u8 eLock;             /* READ_LOCK or WRITE_LOCK */

   489   BtLock *pNext;        /* Next in BtShared.pLock list */

   490 };

   491 

   492 /* Candidate values for BtLock.eLock */

   493 #define READ_LOCK     1

   494 #define WRITE_LOCK    2

   495 

   496 #ifdef SQLITE_OMIT_SHARED_CACHE

   497   /*

   498   ** The functions queryTableLock(), lockTable() and unlockAllTables()

   499   ** manipulate entries in the BtShared.pLock linked list used to store

   500   ** shared-cache table level locks. If the library is compiled with the

   501   ** shared-cache feature disabled, then there is only ever one user

   502   ** of each BtShared structure and so this locking is not necessary. 

   503   ** So define the lock related functions as no-ops.

   504   */

   505   #define queryTableLock(a,b,c) SQLITE_OK

   506   #define lockTable(a,b,c) SQLITE_OK

   507   #define unlockAllTables(a)

   508 #else

   509 

   510 

   511 /*

   512 ** Query to see if btree handle p may obtain a lock of type eLock 

   513 ** (READ_LOCK or WRITE_LOCK) on the table with root-page iTab. Return

   514 ** SQLITE_OK if the lock may be obtained (by calling lockTable()), or

   515 ** SQLITE_LOCKED if not.

   516 */

   517 static int queryTableLock(Btree *p, Pgno iTab, u8 eLock){

   518   BtShared *pBt = p->pBt;

   519   BtLock *pIter;

   520 

   521   /* This is a no-op if the shared-cache is not enabled */

   522   if( 0==sqlite3ThreadDataReadOnly()->useSharedData ){

   523     return SQLITE_OK;

   524   }

   525 

   526   /* This (along with lockTable()) is where the ReadUncommitted flag is

   527   ** dealt with. If the caller is querying for a read-lock and the flag is

   528   ** set, it is unconditionally granted - even if there are write-locks

   529   ** on the table. If a write-lock is requested, the ReadUncommitted flag

   530   ** is not considered.

   531   **

   532   ** In function lockTable(), if a read-lock is demanded and the 

   533   ** ReadUncommitted flag is set, no entry is added to the locks list 

   534   ** (BtShared.pLock).

   535   **

   536   ** To summarize: If the ReadUncommitted flag is set, then read cursors do

   537   ** not create or respect table locks. The locking procedure for a 

   538   ** write-cursor does not change.

   539   */

   540   if( 

   541     !p->pSqlite || 

   542     0==(p->pSqlite->flags&SQLITE_ReadUncommitted) || 

   543     eLock==WRITE_LOCK ||

   544     iTab==MASTER_ROOT

   545   ){

   546     for(pIter=pBt->pLock; pIter; pIter=pIter->pNext){

   547       if( pIter->pBtree!=p && pIter->iTable==iTab && 

   548           (pIter->eLock!=eLock || eLock!=READ_LOCK) ){

   549         return SQLITE_LOCKED;

   550       }

   551     }

   552   }

   553   return SQLITE_OK;

   554 }

   555 

   556 /*

   557 ** Add a lock on the table with root-page iTable to the shared-btree used

   558 ** by Btree handle p. Parameter eLock must be either READ_LOCK or 

   559 ** WRITE_LOCK.

   560 **

   561 ** SQLITE_OK is returned if the lock is added successfully. SQLITE_BUSY and

   562 ** SQLITE_NOMEM may also be returned.

   563 */

   564 static int lockTable(Btree *p, Pgno iTable, u8 eLock){

   565   BtShared *pBt = p->pBt;

   566   BtLock *pLock = 0;

   567   BtLock *pIter;

   568 

   569   /* This is a no-op if the shared-cache is not enabled */

   570   if( 0==sqlite3ThreadDataReadOnly()->useSharedData ){

   571     return SQLITE_OK;

   572   }

   573 

   574   assert( SQLITE_OK==queryTableLock(p, iTable, eLock) );

   575 

   576   /* If the read-uncommitted flag is set and a read-lock is requested,

   577   ** return early without adding an entry to the BtShared.pLock list. See

   578   ** comment in function queryTableLock() for more info on handling 

   579   ** the ReadUncommitted flag.

   580   */

   581   if( 

   582     (p->pSqlite) && 

   583     (p->pSqlite->flags&SQLITE_ReadUncommitted) && 

   584     (eLock==READ_LOCK) &&

   585     iTable!=MASTER_ROOT

   586   ){

   587     return SQLITE_OK;

   588   }

   589 

   590   /* First search the list for an existing lock on this table. */

   591   for(pIter=pBt->pLock; pIter; pIter=pIter->pNext){

   592     if( pIter->iTable==iTable && pIter->pBtree==p ){

   593       pLock = pIter;

   594       break;

   595     }

   596   }

   597 

   598   /* If the above search did not find a BtLock struct associating Btree p

   599   ** with table iTable, allocate one and link it into the list.

   600   */

   601   if( !pLock ){

   602     pLock = (BtLock *)sqliteMalloc(sizeof(BtLock));

   603     if( !pLock ){

   604       return SQLITE_NOMEM;

   605     }

   606     pLock->iTable = iTable;

   607     pLock->pBtree = p;

   608     pLock->pNext = pBt->pLock;

   609     pBt->pLock = pLock;

   610   }

   611 

   612   /* Set the BtLock.eLock variable to the maximum of the current lock

   613   ** and the requested lock. This means if a write-lock was already held

   614   ** and a read-lock requested, we don't incorrectly downgrade the lock.

   615   */

   616   assert( WRITE_LOCK>READ_LOCK );

   617   if( eLock>pLock->eLock ){

   618     pLock->eLock = eLock;

   619   }

   620 

   621   return SQLITE_OK;

   622 }

   623 

   624 /*

   625 ** Release all the table locks (locks obtained via calls to the lockTable()

   626 ** procedure) held by Btree handle p.

   627 */

   628 static void unlockAllTables(Btree *p){

   629   BtLock **ppIter = &p->pBt->pLock;

   630 

   631   /* If the shared-cache extension is not enabled, there should be no

   632   ** locks in the BtShared.pLock list, making this procedure a no-op. Assert

   633   ** that this is the case.

   634   */

   635   assert( sqlite3ThreadDataReadOnly()->useSharedData || 0==*ppIter );

   636 

   637   while( *ppIter ){

   638     BtLock *pLock = *ppIter;

   639     if( pLock->pBtree==p ){

   640       *ppIter = pLock->pNext;

   641       sqliteFree(pLock);

   642     }else{

   643       ppIter = &pLock->pNext;

   644     }

   645   }

   646 }

   647 #endif /* SQLITE_OMIT_SHARED_CACHE */

   648 

   649 static void releasePage(MemPage *pPage);  /* Forward reference */

   650 

   651 /*

   652 ** Save the current cursor position in the variables BtCursor.nKey 

   653 ** and BtCursor.pKey. The cursor's state is set to CURSOR_REQUIRESEEK.

   654 */

   655 static int saveCursorPosition(BtCursor *pCur){

   656   int rc;

   657 

   658   assert( CURSOR_VALID==pCur->eState );

   659   assert( 0==pCur->pKey );

   660 

   661   rc = sqlite3BtreeKeySize(pCur, &pCur->nKey);

   662 

   663   /* If this is an intKey table, then the above call to BtreeKeySize()

   664   ** stores the integer key in pCur->nKey. In this case this value is

   665   ** all that is required. Otherwise, if pCur is not open on an intKey

   666   ** table, then malloc space for and store the pCur->nKey bytes of key 

   667   ** data.

   668   */

   669   if( rc==SQLITE_OK && 0==pCur->pPage->intKey){

   670     void *pKey = sqliteMalloc(pCur->nKey);

   671     if( pKey ){

   672       rc = sqlite3BtreeKey(pCur, 0, pCur->nKey, pKey);

   673       if( rc==SQLITE_OK ){

   674         pCur->pKey = pKey;

   675       }else{

   676         sqliteFree(pKey);

   677       }

   678     }else{

   679       rc = SQLITE_NOMEM;

   680     }

   681   }

   682   assert( !pCur->pPage->intKey || !pCur->pKey );

   683 

   684   if( rc==SQLITE_OK ){

   685     releasePage(pCur->pPage);

   686     pCur->pPage = 0;

   687     pCur->eState = CURSOR_REQUIRESEEK;

   688   }

   689 

   690   return rc;

   691 }

   692 

   693 /*

   694 ** Save the positions of all cursors except pExcept open on the table 

   695 ** with root-page iRoot. Usually, this is called just before cursor

   696 ** pExcept is used to modify the table (BtreeDelete() or BtreeInsert()).

   697 */

   698 static int saveAllCursors(BtShared *pBt, Pgno iRoot, BtCursor *pExcept){

   699   BtCursor *p;

   700   for(p=pBt->pCursor; p; p=p->pNext){

   701     if( p!=pExcept && (0==iRoot || p->pgnoRoot==iRoot) && 

   702         p->eState==CURSOR_VALID ){

   703       int rc = saveCursorPosition(p);

   704       if( SQLITE_OK!=rc ){

   705         return rc;

   706       }

   707     }

   708   }

   709   return SQLITE_OK;

   710 }

   711 

   712 /*

   713 ** Restore the cursor to the position it was in (or as close to as possible)

   714 ** when saveCursorPosition() was called. Note that this call deletes the 

   715 ** saved position info stored by saveCursorPosition(), so there can be

   716 ** at most one effective restoreOrClearCursorPosition() call after each 

   717 ** saveCursorPosition().

   718 **

   719 ** If the second argument argument - doSeek - is false, then instead of 

   720 ** returning the cursor to it's saved position, any saved position is deleted

   721 ** and the cursor state set to CURSOR_INVALID.

   722 */

   723 static int restoreOrClearCursorPositionX(BtCursor *pCur, int doSeek){

   724   int rc = SQLITE_OK;

   725   assert( pCur->eState==CURSOR_REQUIRESEEK );

   726   pCur->eState = CURSOR_INVALID;

   727   if( doSeek ){

   728     rc = sqlite3BtreeMoveto(pCur, pCur->pKey, pCur->nKey, &pCur->skip);

   729   }

   730   if( rc==SQLITE_OK ){

   731     sqliteFree(pCur->pKey);

   732     pCur->pKey = 0;

   733     assert( CURSOR_VALID==pCur->eState || CURSOR_INVALID==pCur->eState );

   734   }

   735   return rc;

   736 }

   737 

   738 #define restoreOrClearCursorPosition(p,x) \

   739   (p->eState==CURSOR_REQUIRESEEK?restoreOrClearCursorPositionX(p,x):SQLITE_OK)

   740 

   741 #ifndef SQLITE_OMIT_AUTOVACUUM

   742 /*

   743 ** These macros define the location of the pointer-map entry for a 

   744 ** database page. The first argument to each is the number of usable

   745 ** bytes on each page of the database (often 1024). The second is the

   746 ** page number to look up in the pointer map.

   747 **

   748 ** PTRMAP_PAGENO returns the database page number of the pointer-map

   749 ** page that stores the required pointer. PTRMAP_PTROFFSET returns

   750 ** the offset of the requested map entry.

   751 **

   752 ** If the pgno argument passed to PTRMAP_PAGENO is a pointer-map page,

   753 ** then pgno is returned. So (pgno==PTRMAP_PAGENO(pgsz, pgno)) can be

   754 ** used to test if pgno is a pointer-map page. PTRMAP_ISPAGE implements

   755 ** this test.

   756 */

   757 #define PTRMAP_PAGENO(pBt, pgno) ptrmapPageno(pBt, pgno)

   758 #define PTRMAP_PTROFFSET(pBt, pgno) (5*(pgno-ptrmapPageno(pBt, pgno)-1))

   759 #define PTRMAP_ISPAGE(pBt, pgno) (PTRMAP_PAGENO((pBt),(pgno))==(pgno))

   760 

   761 static Pgno ptrmapPageno(BtShared *pBt, Pgno pgno){

   762   int nPagesPerMapPage = (pBt->usableSize/5)+1;

   763   int iPtrMap = (pgno-2)/nPagesPerMapPage;

   764   int ret = (iPtrMap*nPagesPerMapPage) + 2; 

   765   if( ret==PENDING_BYTE_PAGE(pBt) ){

   766     ret++;

   767   }

   768   return ret;

   769 }

   770 

   771 /*

   772 ** The pointer map is a lookup table that identifies the parent page for

   773 ** each child page in the database file.  The parent page is the page that

   774 ** contains a pointer to the child.  Every page in the database contains

   775 ** 0 or 1 parent pages.  (In this context 'database page' refers

   776 ** to any page that is not part of the pointer map itself.)  Each pointer map

   777 ** entry consists of a single byte 'type' and a 4 byte parent page number.

   778 ** The PTRMAP_XXX identifiers below are the valid types.

   779 **

   780 ** The purpose of the pointer map is to facility moving pages from one

   781 ** position in the file to another as part of autovacuum.  When a page

   782 ** is moved, the pointer in its parent must be updated to point to the

   783 ** new location.  The pointer map is used to locate the parent page quickly.

   784 **

   785 ** PTRMAP_ROOTPAGE: The database page is a root-page. The page-number is not

   786 **                  used in this case.

   787 **

   788 ** PTRMAP_FREEPAGE: The database page is an unused (free) page. The page-number 

   789 **                  is not used in this case.

   790 **

   791 ** PTRMAP_OVERFLOW1: The database page is the first page in a list of 

   792 **                   overflow pages. The page number identifies the page that

   793 **                   contains the cell with a pointer to this overflow page.

   794 **

   795 ** PTRMAP_OVERFLOW2: The database page is the second or later page in a list of

   796 **                   overflow pages. The page-number identifies the previous

   797 **                   page in the overflow page list.

   798 **

   799 ** PTRMAP_BTREE: The database page is a non-root btree page. The page number

   800 **               identifies the parent page in the btree.

   801 */

   802 #define PTRMAP_ROOTPAGE 1

   803 #define PTRMAP_FREEPAGE 2

   804 #define PTRMAP_OVERFLOW1 3

   805 #define PTRMAP_OVERFLOW2 4

   806 #define PTRMAP_BTREE 5

   807 

   808 /*

   809 ** Write an entry into the pointer map.

   810 **

   811 ** This routine updates the pointer map entry for page number 'key'

   812 ** so that it maps to type 'eType' and parent page number 'pgno'.

   813 ** An error code is returned if something goes wrong, otherwise SQLITE_OK.

   814 */

   815 static int ptrmapPut(BtShared *pBt, Pgno key, u8 eType, Pgno parent){

   816   u8 *pPtrmap;    /* The pointer map page */

   817   Pgno iPtrmap;   /* The pointer map page number */

   818   int offset;     /* Offset in pointer map page */

   819   int rc;

   820 

   821   /* The master-journal page number must never be used as a pointer map page */

   822   assert( 0==PTRMAP_ISPAGE(pBt, PENDING_BYTE_PAGE(pBt)) );

   823 

   824   assert( pBt->autoVacuum );

   825   if( key==0 ){

   826     return SQLITE_CORRUPT_BKPT;

   827   }

   828   iPtrmap = PTRMAP_PAGENO(pBt, key);

   829   rc = sqlite3pager_get(pBt->pPager, iPtrmap, (void **)&pPtrmap);

   830   if( rc!=SQLITE_OK ){

   831     return rc;

   832   }

   833   offset = PTRMAP_PTROFFSET(pBt, key);

   834 

   835   if( eType!=pPtrmap[offset] || get4byte(&pPtrmap[offset+1])!=parent ){

   836     TRACE(("PTRMAP_UPDATE: %d->(%d,%d)\n", key, eType, parent));

   837     rc = sqlite3pager_write(pPtrmap);

   838     if( rc==SQLITE_OK ){

   839       pPtrmap[offset] = eType;

   840       put4byte(&pPtrmap[offset+1], parent);

   841     }

   842   }

   843 

   844   sqlite3pager_unref(pPtrmap);

   845   return rc;

   846 }

   847 

   848 /*

   849 ** Read an entry from the pointer map.

   850 **

   851 ** This routine retrieves the pointer map entry for page 'key', writing

   852 ** the type and parent page number to *pEType and *pPgno respectively.

   853 ** An error code is returned if something goes wrong, otherwise SQLITE_OK.

   854 */

   855 static int ptrmapGet(BtShared *pBt, Pgno key, u8 *pEType, Pgno *pPgno){

   856   int iPtrmap;       /* Pointer map page index */

   857   u8 *pPtrmap;       /* Pointer map page data */

   858   int offset;        /* Offset of entry in pointer map */

   859   int rc;

   860 

   861   iPtrmap = PTRMAP_PAGENO(pBt, key);

   862   rc = sqlite3pager_get(pBt->pPager, iPtrmap, (void **)&pPtrmap);

   863   if( rc!=0 ){

   864     return rc;

   865   }

   866 

   867   offset = PTRMAP_PTROFFSET(pBt, key);

   868   assert( pEType!=0 );

   869   *pEType = pPtrmap[offset];

   870   if( pPgno ) *pPgno = get4byte(&pPtrmap[offset+1]);

   871 

   872   sqlite3pager_unref(pPtrmap);

   873   if( *pEType<1 || *pEType>5 ) return SQLITE_CORRUPT_BKPT;

   874   return SQLITE_OK;

   875 }

   876 

   877 #endif /* SQLITE_OMIT_AUTOVACUUM */

   878 

   879 /*

   880 ** Given a btree page and a cell index (0 means the first cell on

   881 ** the page, 1 means the second cell, and so forth) return a pointer

   882 ** to the cell content.

   883 **

   884 ** This routine works only for pages that do not contain overflow cells.

   885 */

   886 static u8 *findCell(MemPage *pPage, int iCell){

   887   u8 *data = pPage->aData;

   888   assert( iCell>=0 );

   889   assert( iCell<get2byte(&data[pPage->hdrOffset+3]) );

   890   return data + get2byte(&data[pPage->cellOffset+2*iCell]);

   891 }

   892 

   893 /*

   894 ** This a more complex version of findCell() that works for

   895 ** pages that do contain overflow cells.  See insert

   896 */

   897 static u8 *findOverflowCell(MemPage *pPage, int iCell){

   898   int i;

   899   for(i=pPage->nOverflow-1; i>=0; i--){

   900     int k;

   901     struct _OvflCell *pOvfl;

   902     pOvfl = &pPage->aOvfl[i];

   903     k = pOvfl->idx;

   904     if( k<=iCell ){

   905       if( k==iCell ){

   906         return pOvfl->pCell;

   907       }

   908       iCell--;

   909     }

   910   }

   911   return findCell(pPage, iCell);

   912 }

   913 

   914 /*

   915 ** Parse a cell content block and fill in the CellInfo structure.  There

   916 ** are two versions of this function.  parseCell() takes a cell index

   917 ** as the second argument and parseCellPtr() takes a pointer to the

   918 ** body of the cell as its second argument.

   919 */

   920 static void parseCellPtr(

   921   MemPage *pPage,         /* Page containing the cell */

   922   u8 *pCell,              /* Pointer to the cell text. */

   923   CellInfo *pInfo         /* Fill in this structure */

   924 ){

   925   int n;                  /* Number bytes in cell content header */

   926   u32 nPayload;           /* Number of bytes of cell payload */

   927 

   928   pInfo->pCell = pCell;

   929   assert( pPage->leaf==0 || pPage->leaf==1 );

   930   n = pPage->childPtrSize;

   931   assert( n==4-4*pPage->leaf );

   932   if( pPage->hasData ){

   933     n += getVarint32(&pCell[n], &nPayload);

   934   }else{

   935     nPayload = 0;

   936   }

   937   pInfo->nData = nPayload;

   938   if( pPage->intKey ){

   939     n += getVarint(&pCell[n], (u64 *)&pInfo->nKey);

   940   }else{

   941     u32 x;

   942     n += getVarint32(&pCell[n], &x);

   943     pInfo->nKey = x;

   944     nPayload += x;

   945   }

   946   pInfo->nHeader = n;

   947   if( nPayload<=pPage->maxLocal ){

   948     /* This is the (easy) common case where the entire payload fits

   949     ** on the local page.  No overflow is required.

   950     */

   951     int nSize;          /* Total size of cell content in bytes */

   952     pInfo->nLocal = nPayload;

   953     pInfo->iOverflow = 0;

   954     nSize = nPayload + n;

   955     if( nSize<4 ){

   956       nSize = 4;        /* Minimum cell size is 4 */

   957     }

   958     pInfo->nSize = nSize;

   959   }else{

   960     /* If the payload will not fit completely on the local page, we have

   961     ** to decide how much to store locally and how much to spill onto

   962     ** overflow pages.  The strategy is to minimize the amount of unused

   963     ** space on overflow pages while keeping the amount of local storage

   964     ** in between minLocal and maxLocal.

   965     **

   966     ** Warning:  changing the way overflow payload is distributed in any

   967     ** way will result in an incompatible file format.

   968     */

   969     int minLocal;  /* Minimum amount of payload held locally */

   970     int maxLocal;  /* Maximum amount of payload held locally */

   971     int surplus;   /* Overflow payload available for local storage */

   972 

   973     minLocal = pPage->minLocal;

   974     maxLocal = pPage->maxLocal;

   975     surplus = minLocal + (nPayload - minLocal)%(pPage->pBt->usableSize - 4);

   976     if( surplus <= maxLocal ){

   977       pInfo->nLocal = surplus;

   978     }else{

   979       pInfo->nLocal = minLocal;

   980     }

   981     pInfo->iOverflow = pInfo->nLocal + n;

   982     pInfo->nSize = pInfo->iOverflow + 4;

   983   }

   984 }

   985 static void parseCell(

   986   MemPage *pPage,         /* Page containing the cell */

   987   int iCell,              /* The cell index.  First cell is 0 */

   988   CellInfo *pInfo         /* Fill in this structure */

   989 ){

   990   parseCellPtr(pPage, findCell(pPage, iCell), pInfo);

   991 }

   992 

   993 /*

   994 ** Compute the total number of bytes that a Cell needs in the cell

   995 ** data area of the btree-page.  The return number includes the cell

   996 ** data header and the local payload, but not any overflow page or

   997 ** the space used by the cell pointer.

   998 */

   999 #ifndef NDEBUG

  1000 static int cellSize(MemPage *pPage, int iCell){

  1001   CellInfo info;

  1002   parseCell(pPage, iCell, &info);

  1003   return info.nSize;

  1004 }

  1005 #endif

  1006 static int cellSizePtr(MemPage *pPage, u8 *pCell){

  1007   CellInfo info;

  1008   parseCellPtr(pPage, pCell, &info);

  1009   return info.nSize;

  1010 }

  1011 

  1012 #ifndef SQLITE_OMIT_AUTOVACUUM

  1013 /*

  1014 ** If the cell pCell, part of page pPage contains a pointer

  1015 ** to an overflow page, insert an entry into the pointer-map

  1016 ** for the overflow page.

  1017 */

  1018 static int ptrmapPutOvflPtr(MemPage *pPage, u8 *pCell){

  1019   if( pCell ){

  1020     CellInfo info;

  1021     parseCellPtr(pPage, pCell, &info);

  1022     if( (info.nData+(pPage->intKey?0:info.nKey))>info.nLocal ){

  1023       Pgno ovfl = get4byte(&pCell[info.iOverflow]);

  1024       return ptrmapPut(pPage->pBt, ovfl, PTRMAP_OVERFLOW1, pPage->pgno);

  1025     }

  1026   }

  1027   return SQLITE_OK;

  1028 }

  1029 /*

  1030 ** If the cell with index iCell on page pPage contains a pointer

  1031 ** to an overflow page, insert an entry into the pointer-map

  1032 ** for the overflow page.

  1033 */

  1034 static int ptrmapPutOvfl(MemPage *pPage, int iCell){

  1035   u8 *pCell;

  1036   pCell = findOverflowCell(pPage, iCell);

  1037   return ptrmapPutOvflPtr(pPage, pCell);

  1038 }

  1039 #endif

  1040 

  1041 

  1042 /*

  1043 ** Do sanity checking on a page.  Throw an exception if anything is

  1044 ** not right.

  1045 **

  1046 ** This routine is used for internal error checking only.  It is omitted

  1047 ** from most builds.

  1048 */

  1049 #if defined(BTREE_DEBUG) && !defined(NDEBUG) && 0

  1050 static void _pageIntegrity(MemPage *pPage){

  1051   int usableSize;

  1052   u8 *data;

  1053   int i, j, idx, c, pc, hdr, nFree;

  1054   int cellOffset;

  1055   int nCell, cellLimit;

  1056   u8 *used;

  1057 

  1058   used = sqliteMallocRaw( pPage->pBt->pageSize );

  1059   if( used==0 ) return;

  1060   usableSize = pPage->pBt->usableSize;

  1061   assert( pPage->aData==&((unsigned char*)pPage)[-pPage->pBt->pageSize] );

  1062   hdr = pPage->hdrOffset;

  1063   assert( hdr==(pPage->pgno==1 ? 100 : 0) );

  1064   assert( pPage->pgno==sqlite3pager_pagenumber(pPage->aData) );

  1065   c = pPage->aData[hdr];

  1066   if( pPage->isInit ){

  1067     assert( pPage->leaf == ((c & PTF_LEAF)!=0) );

  1068     assert( pPage->zeroData == ((c & PTF_ZERODATA)!=0) );

  1069     assert( pPage->leafData == ((c & PTF_LEAFDATA)!=0) );

  1070     assert( pPage->intKey == ((c & (PTF_INTKEY|PTF_LEAFDATA))!=0) );

  1071     assert( pPage->hasData ==

  1072              !(pPage->zeroData || (!pPage->leaf && pPage->leafData)) );

  1073     assert( pPage->cellOffset==pPage->hdrOffset+12-4*pPage->leaf );

  1074     assert( pPage->nCell = get2byte(&pPage->aData[hdr+3]) );

  1075   }

  1076   data = pPage->aData;

  1077   memset(used, 0, usableSize);

  1078   for(i=0; i<hdr+10-pPage->leaf*4; i++) used[i] = 1;

  1079   nFree = 0;

  1080   pc = get2byte(&data[hdr+1]);

  1081   while( pc ){

  1082     int size;

  1083     assert( pc>0 && pc<usableSize-4 );

  1084     size = get2byte(&data[pc+2]);

  1085     assert( pc+size<=usableSize );

  1086     nFree += size;

  1087     for(i=pc; i<pc+size; i++){

  1088       assert( used[i]==0 );

  1089       used[i] = 1;

  1090     }

  1091     pc = get2byte(&data[pc]);

  1092   }

  1093   idx = 0;

  1094   nCell = get2byte(&data[hdr+3]);

  1095   cellLimit = get2byte(&data[hdr+5]);

  1096   assert( pPage->isInit==0 

  1097          || pPage->nFree==nFree+data[hdr+7]+cellLimit-(cellOffset+2*nCell) );

  1098   cellOffset = pPage->cellOffset;

  1099   for(i=0; i<nCell; i++){

  1100     int size;

  1101     pc = get2byte(&data[cellOffset+2*i]);

  1102     assert( pc>0 && pc<usableSize-4 );

  1103     size = cellSize(pPage, &data[pc]);

  1104     assert( pc+size<=usableSize );

  1105     for(j=pc; j<pc+size; j++){

  1106       assert( used[j]==0 );

  1107       used[j] = 1;

  1108     }

  1109   }

  1110   for(i=cellOffset+2*nCell; i<cellimit; i++){

  1111     assert( used[i]==0 );

  1112     used[i] = 1;

  1113   }

  1114   nFree = 0;

  1115   for(i=0; i<usableSize; i++){

  1116     assert( used[i]<=1 );

  1117     if( used[i]==0 ) nFree++;

  1118   }

  1119   assert( nFree==data[hdr+7] );

  1120   sqliteFree(used);

  1121 }

  1122 #define pageIntegrity(X) _pageIntegrity(X)

  1123 #else

  1124 # define pageIntegrity(X)

  1125 #endif

  1126 

  1127 /* A bunch of assert() statements to check the transaction state variables

  1128 ** of handle p (type Btree*) are internally consistent.

  1129 */

  1130 #define btreeIntegrity(p) \

  1131   assert( p->inTrans!=TRANS_NONE || p->pBt->nTransaction<p->pBt->nRef ); \

  1132   assert( p->pBt->nTransaction<=p->pBt->nRef ); \

  1133   assert( p->pBt->inTransaction!=TRANS_NONE || p->pBt->nTransaction==0 ); \

  1134   assert( p->pBt->inTransaction>=p->inTrans ); 

  1135