summaryrefslogtreecommitdiffstats
path: root/kopete/plugins/statistics/sqlite/btree.c
diff options
context:
space:
mode:
Diffstat (limited to 'kopete/plugins/statistics/sqlite/btree.c')
-rw-r--r--kopete/plugins/statistics/sqlite/btree.c4462
1 files changed, 0 insertions, 4462 deletions
diff --git a/kopete/plugins/statistics/sqlite/btree.c b/kopete/plugins/statistics/sqlite/btree.c
deleted file mode 100644
index fe8754e0..00000000
--- a/kopete/plugins/statistics/sqlite/btree.c
+++ /dev/null
@@ -1,4462 +0,0 @@
-/*
-** 2004 April 6
-**
-** The author disclaims copyright to this source code. In place of
-** a legal notice, here is a blessing:
-**
-** May you do good and not evil.
-** May you find forgiveness for yourself and forgive others.
-** May you share freely, never taking more than you give.
-**
-*************************************************************************
-** $Id$
-**
-** This file implements a external (disk-based) database using BTrees.
-** For a detailed discussion of BTrees, refer to
-**
-** Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
-** "Sorting And Searching", pages 473-480. Addison-Wesley
-** Publishing Company, Reading, Massachusetts.
-**
-** The basic idea is that each page of the file contains N database
-** entries and N+1 pointers to subpages.
-**
-** ----------------------------------------------------------------
-** | Ptr(0) | Key(0) | Ptr(1) | Key(1) | ... | Key(N) | Ptr(N+1) |
-** ----------------------------------------------------------------
-**
-** All of the keys on the page that Ptr(0) points to have values less
-** than Key(0). All of the keys on page Ptr(1) and its subpages have
-** values greater than Key(0) and less than Key(1). All of the keys
-** on Ptr(N+1) and its subpages have values greater than Key(N). And
-** so forth.
-**
-** Finding a particular key requires reading O(log(M)) pages from the
-** disk where M is the number of entries in the tree.
-**
-** In this implementation, a single file can hold one or more separate
-** BTrees. Each BTree is identified by the index of its root page. The
-** key and data for any entry are combined to form the "payload". A
-** fixed amount of payload can be carried directly on the database
-** page. If the payload is larger than the preset amount then surplus
-** bytes are stored on overflow pages. The payload for an entry
-** and the preceding pointer are combined to form a "Cell". Each
-** page has a small header which contains the Ptr(N+1) pointer and other
-** information such as the size of key and data.
-**
-** FORMAT DETAILS
-**
-** The file is divided into pages. The first page is called page 1,
-** the second is page 2, and so forth. A page number of zero indicates
-** "no such page". The page size can be anything between 512 and 65536.
-** Each page can be either a btree page, a freelist page or an overflow
-** page.
-**
-** The first page is always a btree page. The first 100 bytes of the first
-** page contain a special header (the "file header") that describes the file.
-** The format of the file header is as follows:
-**
-** OFFSET SIZE DESCRIPTION
-** 0 16 Header string: "SQLite format 3\000"
-** 16 2 Page size in bytes.
-** 18 1 File format write version
-** 19 1 File format read version
-** 20 1 Bytes of unused space at the end of each page
-** 21 1 Max embedded payload fraction
-** 22 1 Min embedded payload fraction
-** 23 1 Min leaf payload fraction
-** 24 4 File change counter
-** 28 4 Reserved for future use
-** 32 4 First freelist page
-** 36 4 Number of freelist pages in the file
-** 40 60 15 4-byte meta values passed to higher layers
-**
-** All of the integer values are big-endian (most significant byte first).
-**
-** The file change counter is incremented when the database is changed more
-** than once within the same second. This counter, together with the
-** modification time of the file, allows other processes to know
-** when the file has changed and thus when they need to flush their
-** cache.
-**
-** The max embedded payload fraction is the amount of the total usable
-** space in a page that can be consumed by a single cell for standard
-** B-tree (non-LEAFDATA) tables. A value of 255 means 100%. The default
-** is to limit the maximum cell size so that at least 4 cells will fit
-** on one page. Thus the default max embedded payload fraction is 64.
-**
-** If the payload for a cell is larger than the max payload, then extra
-** payload is spilled to overflow pages. Once an overflow page is allocated,
-** as many bytes as possible are moved into the overflow pages without letting
-** the cell size drop below the min embedded payload fraction.
-**
-** The min leaf payload fraction is like the min embedded payload fraction
-** except that it applies to leaf nodes in a LEAFDATA tree. The maximum
-** payload fraction for a LEAFDATA tree is always 100% (or 255) and it
-** not specified in the header.
-**
-** Each btree pages is divided into three sections: The header, the
-** cell pointer array, and the cell area area. Page 1 also has a 100-byte
-** file header that occurs before the page header.
-**
-** |----------------|
-** | file header | 100 bytes. Page 1 only.
-** |----------------|
-** | page header | 8 bytes for leaves. 12 bytes for interior nodes
-** |----------------|
-** | cell pointer | | 2 bytes per cell. Sorted order.
-** | array | | Grows downward
-** | | v
-** |----------------|
-** | unallocated |
-** | space |
-** |----------------| ^ Grows upwards
-** | cell content | | Arbitrary order interspersed with freeblocks.
-** | area | | and free space fragments.
-** |----------------|
-**
-** The page headers looks like this:
-**
-** OFFSET SIZE DESCRIPTION
-** 0 1 Flags. 1: intkey, 2: zerodata, 4: leafdata, 8: leaf
-** 1 2 byte offset to the first freeblock
-** 3 2 number of cells on this page
-** 5 2 first byte of the cell content area
-** 7 1 number of fragmented free bytes
-** 8 4 Right child (the Ptr(N+1) value). Omitted on leaves.
-**
-** The flags define the format of this btree page. The leaf flag means that
-** this page has no children. The zerodata flag means that this page carries
-** only keys and no data. The intkey flag means that the key is a integer
-** which is stored in the key size entry of the cell header rather than in
-** the payload area.
-**
-** The cell pointer array begins on the first byte after the page header.
-** The cell pointer array contains zero or more 2-byte numbers which are
-** offsets from the beginning of the page to the cell content in the cell
-** content area. The cell pointers occur in sorted order. The system strives
-** to keep free space after the last cell pointer so that new cells can
-** be easily added without having to defragment the page.
-**
-** Cell content is stored at the very end of the page and grows toward the
-** beginning of the page.
-**
-** Unused space within the cell content area is collected into a linked list of
-** freeblocks. Each freeblock is at least 4 bytes in size. The byte offset
-** to the first freeblock is given in the header. Freeblocks occur in
-** increasing order. Because a freeblock must be at least 4 bytes in size,
-** any group of 3 or fewer unused bytes in the cell content area cannot
-** exist on the freeblock chain. A group of 3 or fewer free bytes is called
-** a fragment. The total number of bytes in all fragments is recorded.
-** in the page header at offset 7.
-**
-** SIZE DESCRIPTION
-** 2 Byte offset of the next freeblock
-** 2 Bytes in this freeblock
-**
-** Cells are of variable length. Cells are stored in the cell content area at
-** the end of the page. Pointers to the cells are in the cell pointer array
-** that immediately follows the page header. Cells is not necessarily
-** contiguous or in order, but cell pointers are contiguous and in order.
-**
-** Cell content makes use of variable length integers. A variable
-** length integer is 1 to 9 bytes where the lower 7 bits of each
-** byte are used. The integer consists of all bytes that have bit 8 set and
-** the first byte with bit 8 clear. The most significant byte of the integer
-** appears first. A variable-length integer may not be more than 9 bytes long.
-** As a special case, all 8 bytes of the 9th byte are used as data. This
-** allows a 64-bit integer to be encoded in 9 bytes.
-**
-** 0x00 becomes 0x00000000
-** 0x7f becomes 0x0000007f
-** 0x81 0x00 becomes 0x00000080
-** 0x82 0x00 becomes 0x00000100
-** 0x80 0x7f becomes 0x0000007f
-** 0x8a 0x91 0xd1 0xac 0x78 becomes 0x12345678
-** 0x81 0x81 0x81 0x81 0x01 becomes 0x10204081
-**
-** Variable length integers are used for rowids and to hold the number of
-** bytes of key and data in a btree cell.
-**
-** The content of a cell looks like this:
-**
-** SIZE DESCRIPTION
-** 4 Page number of the left child. Omitted if leaf flag is set.
-** var Number of bytes of data. Omitted if the zerodata flag is set.
-** var Number of bytes of key. Or the key itself if intkey flag is set.
-** * Payload
-** 4 First page of the overflow chain. Omitted if no overflow
-**
-** Overflow pages form a linked list. Each page except the last is completely
-** filled with data (pagesize - 4 bytes). The last page can have as little
-** as 1 byte of data.
-**
-** SIZE DESCRIPTION
-** 4 Page number of next overflow page
-** * Data
-**
-** Freelist pages come in two subtypes: trunk pages and leaf pages. The
-** file header points to first in a linked list of trunk page. Each trunk
-** page points to multiple leaf pages. The content of a leaf page is
-** unspecified. A trunk page looks like this:
-**
-** SIZE DESCRIPTION
-** 4 Page number of next trunk page
-** 4 Number of leaf pointers on this page
-** * zero or more pages numbers of leaves
-*/
-#include "sqliteInt.h"
-#include "pager.h"
-#include "btree.h"
-#include "os.h"
-#include <assert.h>
-
-
-/* The following value is the maximum cell size assuming a maximum page
-** size give above.
-*/
-#define MX_CELL_SIZE(pBt) (pBt->pageSize-8)
-
-/* The maximum number of cells on a single page of the database. This
-** assumes a minimum cell size of 3 bytes. Such small cells will be
-** exceedingly rare, but they are possible.
-*/
-#define MX_CELL(pBt) ((pBt->pageSize-8)/3)
-
-/* Forward declarations */
-typedef struct MemPage MemPage;
-
-/*
-** This is a magic string that appears at the beginning of every
-** SQLite database in order to identify the file as a real database.
-** 123456789 123456 */
-static const char zMagicHeader[] = "SQLite format 3";
-
-/*
-** Page type flags. An ORed combination of these flags appear as the
-** first byte of every BTree page.
-*/
-#define PTF_INTKEY 0x01
-#define PTF_ZERODATA 0x02
-#define PTF_LEAFDATA 0x04
-#define PTF_LEAF 0x08
-
-/*
-** As each page of the file is loaded into memory, an instance of the following
-** structure is appended and initialized to zero. This structure stores
-** information about the page that is decoded from the raw file page.
-**
-** The pParent field points back to the parent page. This allows us to
-** walk up the BTree from any leaf to the root. Care must be taken to
-** unref() the parent page pointer when this page is no longer referenced.
-** The pageDestructor() routine handles that chore.
-*/
-struct MemPage {
- u8 isInit; /* True if previously initialized. MUST BE FIRST! */
- u8 idxShift; /* True if Cell indices have changed */
- u8 nOverflow; /* Number of overflow cell bodies in aCell[] */
- u8 intKey; /* True if intkey flag is set */
- u8 leaf; /* True if leaf flag is set */
- u8 zeroData; /* True if table stores keys only */
- u8 leafData; /* True if tables stores data on leaves only */
- u8 hasData; /* True if this page stores data */
- u8 hdrOffset; /* 100 for page 1. 0 otherwise */
- u8 childPtrSize; /* 0 if leaf==1. 4 if leaf==0 */
- u16 maxLocal; /* Copy of Btree.maxLocal or Btree.maxLeaf */
- u16 minLocal; /* Copy of Btree.minLocal or Btree.minLeaf */
- u16 cellOffset; /* Index in aData of first cell pointer */
- u16 idxParent; /* Index in parent of this node */
- u16 nFree; /* Number of free bytes on the page */
- u16 nCell; /* Number of cells on this page, local and ovfl */
- struct _OvflCell { /* Cells that will not fit on aData[] */
- u8 *pCell; /* Pointers to the body of the overflow cell */
- u16 idx; /* Insert this cell before idx-th non-overflow cell */
- } aOvfl[5];
- struct Btree *pBt; /* Pointer back to BTree structure */
- u8 *aData; /* Pointer back to the start of the page */
- Pgno pgno; /* Page number for this page */
- MemPage *pParent; /* The parent of this page. NULL for root */
-};
-
-/*
-** The in-memory image of a disk page has the auxiliary information appended
-** to the end. EXTRA_SIZE is the number of bytes of space needed to hold
-** that extra information.
-*/
-#define EXTRA_SIZE sizeof(MemPage)
-
-/*
-** Everything we need to know about an open database
-*/
-struct Btree {
- Pager *pPager; /* The page cache */
- BtCursor *pCursor; /* A list of all open cursors */
- MemPage *pPage1; /* First page of the database */
- u8 inTrans; /* True if a transaction is in progress */
- u8 inStmt; /* True if we are in a statement subtransaction */
- u8 readOnly; /* True if the underlying file is readonly */
- u8 maxEmbedFrac; /* Maximum payload as % of total page size */
- u8 minEmbedFrac; /* Minimum payload as % of total page size */
- u8 minLeafFrac; /* Minimum leaf payload as % of total page size */
- u8 pageSizeFixed; /* True if the page size can no longer be changed */
- u16 pageSize; /* Total number of bytes on a page */
- u16 usableSize; /* Number of usable bytes on each page */
- int maxLocal; /* Maximum local payload in non-LEAFDATA tables */
- int minLocal; /* Minimum local payload in non-LEAFDATA tables */
- int maxLeaf; /* Maximum local payload in a LEAFDATA table */
- int minLeaf; /* Minimum local payload in a LEAFDATA table */
-};
-typedef Btree Bt;
-
-/*
-** Btree.inTrans may take one of the following values.
-*/
-#define TRANS_NONE 0
-#define TRANS_READ 1
-#define TRANS_WRITE 2
-
-/*
-** An instance of the following structure is used to hold information
-** about a cell. The parseCellPtr() function fills in this structure
-** based on information extract from the raw disk page.
-*/
-typedef struct CellInfo CellInfo;
-struct CellInfo {
- u8 *pCell; /* Pointer to the start of cell content */
- i64 nKey; /* The key for INTKEY tables, or number of bytes in key */
- u32 nData; /* Number of bytes of data */
- u16 nHeader; /* Size of the cell content header in bytes */
- u16 nLocal; /* Amount of payload held locally */
- u16 iOverflow; /* Offset to overflow page number. Zero if no overflow */
- u16 nSize; /* Size of the cell content on the main b-tree page */
-};
-
-/*
-** A cursor is a pointer to a particular entry in the BTree.
-** The entry is identified by its MemPage and the index in
-** MemPage.aCell[] of the entry.
-*/
-struct BtCursor {
- Btree *pBt; /* The Btree to which this cursor belongs */
- BtCursor *pNext, *pPrev; /* Forms a linked list of all cursors */
- int (*xCompare)(void*,int,const void*,int,const void*); /* Key comp func */
- void *pArg; /* First arg to xCompare() */
- Pgno pgnoRoot; /* The root page of this tree */
- MemPage *pPage; /* Page that contains the entry */
- int idx; /* Index of the entry in pPage->aCell[] */
- CellInfo info; /* A parse of the cell we are pointing at */
- u8 wrFlag; /* True if writable */
- u8 isValid; /* TRUE if points to a valid entry */
- u8 status; /* Set to SQLITE_ABORT if cursors is invalidated */
-};
-
-/*
-** Forward declaration
-*/
-static int checkReadLocks(Btree*,Pgno,BtCursor*);
-
-
-/*
-** Read or write a two- and four-byte big-endian integer values.
-*/
-static u32 get2byte(unsigned char *p){
- return (p[0]<<8) | p[1];
-}
-static u32 get4byte(unsigned char *p){
- return (p[0]<<24) | (p[1]<<16) | (p[2]<<8) | p[3];
-}
-static void put2byte(unsigned char *p, u32 v){
- p[0] = v>>8;
- p[1] = v;
-}
-static void put4byte(unsigned char *p, u32 v){
- p[0] = v>>24;
- p[1] = v>>16;
- p[2] = v>>8;
- p[3] = v;
-}
-
-/*
-** Routines to read and write variable-length integers. These used to
-** be defined locally, but now we use the varint routines in the util.c
-** file.
-*/
-#define getVarint sqlite3GetVarint
-#define getVarint32 sqlite3GetVarint32
-#define putVarint sqlite3PutVarint
-
-/*
-** Given a btree page and a cell index (0 means the first cell on
-** the page, 1 means the second cell, and so forth) return a pointer
-** to the cell content.
-**
-** This routine works only for pages that do not contain overflow cells.
-*/
-static u8 *findCell(MemPage *pPage, int iCell){
- u8 *data = pPage->aData;
- assert( iCell>=0 );
- assert( iCell<get2byte(&data[pPage->hdrOffset+3]) );
- return data + get2byte(&data[pPage->cellOffset+2*iCell]);
-}
-
-/*
-** This a more complex version of findCell() that works for
-** pages that do contain overflow cells. See insert
-*/
-static u8 *findOverflowCell(MemPage *pPage, int iCell){
- int i;
- for(i=pPage->nOverflow-1; i>=0; i--){
- int k;
- struct _OvflCell *pOvfl;
- pOvfl = &pPage->aOvfl[i];
- k = pOvfl->idx;
- if( k<=iCell ){
- if( k==iCell ){
- return pOvfl->pCell;
- }
- iCell--;
- }
- }
- return findCell(pPage, iCell);
-}
-
-/*
-** Parse a cell content block and fill in the CellInfo structure. There
-** are two versions of this function. parseCell() takes a cell index
-** as the second argument and parseCellPtr() takes a pointer to the
-** body of the cell as its second argument.
-*/
-static void parseCellPtr(
- MemPage *pPage, /* Page containing the cell */
- u8 *pCell, /* Pointer to the cell text. */
- CellInfo *pInfo /* Fill in this structure */
-){
- int n; /* Number bytes in cell content header */
- u32 nPayload; /* Number of bytes of cell payload */
-
- pInfo->pCell = pCell;
- assert( pPage->leaf==0 || pPage->leaf==1 );
- n = pPage->childPtrSize;
- assert( n==4-4*pPage->leaf );
- if( pPage->hasData ){
- n += getVarint32(&pCell[n], &nPayload);
- }else{
- nPayload = 0;
- }
- n += getVarint(&pCell[n], (u64 *)&pInfo->nKey);
- pInfo->nHeader = n;
- pInfo->nData = nPayload;
- if( !pPage->intKey ){
- nPayload += pInfo->nKey;
- }
- if( nPayload<=pPage->maxLocal ){
- /* This is the (easy) common case where the entire payload fits
- ** on the local page. No overflow is required.
- */
- int nSize; /* Total size of cell content in bytes */
- pInfo->nLocal = nPayload;
- pInfo->iOverflow = 0;
- nSize = nPayload + n;
- if( nSize<4 ){
- nSize = 4; /* Minimum cell size is 4 */
- }
- pInfo->nSize = nSize;
- }else{
- /* If the payload will not fit completely on the local page, we have
- ** to decide how much to store locally and how much to spill onto
- ** overflow pages. The strategy is to minimize the amount of unused
- ** space on overflow pages while keeping the amount of local storage
- ** in between minLocal and maxLocal.
- **
- ** Warning: changing the way overflow payload is distributed in any
- ** way will result in an incompatible file format.
- */
- int minLocal; /* Minimum amount of payload held locally */
- int maxLocal; /* Maximum amount of payload held locally */
- int surplus; /* Overflow payload available for local storage */
-
- minLocal = pPage->minLocal;
- maxLocal = pPage->maxLocal;
- surplus = minLocal + (nPayload - minLocal)%(pPage->pBt->usableSize - 4);
- if( surplus <= maxLocal ){
- pInfo->nLocal = surplus;
- }else{
- pInfo->nLocal = minLocal;
- }
- pInfo->iOverflow = pInfo->nLocal + n;
- pInfo->nSize = pInfo->iOverflow + 4;
- }
-}
-static void parseCell(
- MemPage *pPage, /* Page containing the cell */
- int iCell, /* The cell index. First cell is 0 */
- CellInfo *pInfo /* Fill in this structure */
-){
- parseCellPtr(pPage, findCell(pPage, iCell), pInfo);
-}
-
-/*
-** Compute the total number of bytes that a Cell needs in the cell
-** data area of the btree-page. The return number includes the cell
-** data header and the local payload, but not any overflow page or
-** the space used by the cell pointer.
-*/
-#ifndef NDEBUG
-static int cellSize(MemPage *pPage, int iCell){
- CellInfo info;
- parseCell(pPage, iCell, &info);
- return info.nSize;
-}
-#endif
-static int cellSizePtr(MemPage *pPage, u8 *pCell){
- CellInfo info;
- parseCellPtr(pPage, pCell, &info);
- return info.nSize;
-}
-
-/*
-** Do sanity checking on a page. Throw an exception if anything is
-** not right.
-**
-** This routine is used for internal error checking only. It is omitted
-** from most builds.
-*/
-#if defined(BTREE_DEBUG) && !defined(NDEBUG) && 0
-static void _pageIntegrity(MemPage *pPage){
- int usableSize;
- u8 *data;
- int i, j, idx, c, pc, hdr, nFree;
- int cellOffset;
- int nCell, cellLimit;
- u8 *used;
-
- used = sqliteMallocRaw( pPage->pBt->pageSize );
- if( used==0 ) return;
- usableSize = pPage->pBt->usableSize;
- assert( pPage->aData==&((unsigned char*)pPage)[-pPage->pBt->pageSize] );
- hdr = pPage->hdrOffset;
- assert( hdr==(pPage->pgno==1 ? 100 : 0) );
- assert( pPage->pgno==sqlite3pager_pagenumber(pPage->aData) );
- c = pPage->aData[hdr];
- if( pPage->isInit ){
- assert( pPage->leaf == ((c & PTF_LEAF)!=0) );
- assert( pPage->zeroData == ((c & PTF_ZERODATA)!=0) );
- assert( pPage->leafData == ((c & PTF_LEAFDATA)!=0) );
- assert( pPage->intKey == ((c & (PTF_INTKEY|PTF_LEAFDATA))!=0) );
- assert( pPage->hasData ==
- !(pPage->zeroData || (!pPage->leaf && pPage->leafData)) );
- assert( pPage->cellOffset==pPage->hdrOffset+12-4*pPage->leaf );
- assert( pPage->nCell = get2byte(&pPage->aData[hdr+3]) );
- }
- data = pPage->aData;
- memset(used, 0, usableSize);
- for(i=0; i<hdr+10-pPage->leaf*4; i++) used[i] = 1;
- nFree = 0;
- pc = get2byte(&data[hdr+1]);
- while( pc ){
- int size;
- assert( pc>0 && pc<usableSize-4 );
- size = get2byte(&data[pc+2]);
- assert( pc+size<=usableSize );
- nFree += size;
- for(i=pc; i<pc+size; i++){
- assert( used[i]==0 );
- used[i] = 1;
- }
- pc = get2byte(&data[pc]);
- }
- idx = 0;
- nCell = get2byte(&data[hdr+3]);
- cellLimit = get2byte(&data[hdr+5]);
- assert( pPage->isInit==0
- || pPage->nFree==nFree+data[hdr+7]+cellLimit-(cellOffset+2*nCell) );
- cellOffset = pPage->cellOffset;
- for(i=0; i<nCell; i++){
- int size;
- pc = get2byte(&data[cellOffset+2*i]);
- assert( pc>0 && pc<usableSize-4 );
- size = cellSize(pPage, &data[pc]);
- assert( pc+size<=usableSize );
- for(j=pc; j<pc+size; j++){
- assert( used[j]==0 );
- used[j] = 1;
- }
- }
- for(i=cellOffset+2*nCell; i<cellimit; i++){
- assert( used[i]==0 );
- used[i] = 1;
- }
- nFree = 0;
- for(i=0; i<usableSize; i++){
- assert( used[i]<=1 );
- if( used[i]==0 ) nFree++;
- }
- assert( nFree==data[hdr+7] );
- sqliteFree(used);
-}
-#define pageIntegrity(X) _pageIntegrity(X)
-#else
-# define pageIntegrity(X)
-#endif
-
-/*
-** Defragment the page given. All Cells are moved to the
-** beginning of the page and all free space is collected
-** into one big FreeBlk at the end of the page.
-*/
-static int defragmentPage(MemPage *pPage){
- int i; /* Loop counter */
- int pc; /* Address of a i-th cell */
- int addr; /* Offset of first byte after cell pointer array */
- int hdr; /* Offset to the page header */
- int size; /* Size of a cell */
- int usableSize; /* Number of usable bytes on a page */
- int cellOffset; /* Offset to the cell pointer array */
- int brk; /* Offset to the cell content area */
- int nCell; /* Number of cells on the page */
- unsigned char *data; /* The page data */
- unsigned char *temp; /* Temp area for cell content */
-
- assert( sqlite3pager_iswriteable(pPage->aData) );
- assert( pPage->pBt!=0 );
- assert( pPage->pBt->usableSize <= SQLITE_MAX_PAGE_SIZE );
- assert( pPage->nOverflow==0 );
- temp = sqliteMalloc( pPage->pBt->pageSize );
- if( temp==0 ) return SQLITE_NOMEM;
- data = pPage->aData;
- hdr = pPage->hdrOffset;
- cellOffset = pPage->cellOffset;
- nCell = pPage->nCell;
- assert( nCell==get2byte(&data[hdr+3]) );
- usableSize = pPage->pBt->usableSize;
- brk = get2byte(&data[hdr+5]);
- memcpy(&temp[brk], &data[brk], usableSize - brk);
- brk = usableSize;
- for(i=0; i<nCell; i++){
- u8 *pAddr; /* The i-th cell pointer */
- pAddr = &data[cellOffset + i*2];
- pc = get2byte(pAddr);
- assert( pc<pPage->pBt->usableSize );
- size = cellSizePtr(pPage, &temp[pc]);
- brk -= size;
- memcpy(&data[brk], &temp[pc], size);
- put2byte(pAddr, brk);
- }
- assert( brk>=cellOffset+2*nCell );
- put2byte(&data[hdr+5], brk);
- data[hdr+1] = 0;
- data[hdr+2] = 0;
- data[hdr+7] = 0;
- addr = cellOffset+2*nCell;
- memset(&data[addr], 0, brk-addr);
- sqliteFree(temp);
- return SQLITE_OK;
-}
-
-/*
-** Allocate nByte bytes of space on a page.
-**
-** Return the index into pPage->aData[] of the first byte of
-** the new allocation. Or return 0 if there is not enough free
-** space on the page to satisfy the allocation request.
-**
-** If the page contains nBytes of free space but does not contain
-** nBytes of contiguous free space, then this routine automatically
-** calls defragementPage() to consolidate all free space before
-** allocating the new chunk.
-*/
-static int allocateSpace(MemPage *pPage, int nByte){
- int addr, pc, hdr;
- int size;
- int nFrag;
- int top;
- int nCell;
- int cellOffset;
- unsigned char *data;
-
- data = pPage->aData;
- assert( sqlite3pager_iswriteable(data) );
- assert( pPage->pBt );
- if( nByte<4 ) nByte = 4;
- if( pPage->nFree<nByte || pPage->nOverflow>0 ) return 0;
- pPage->nFree -= nByte;
- hdr = pPage->hdrOffset;
-
- nFrag = data[hdr+7];
- if( nFrag<60 ){
- /* Search the freelist looking for a slot big enough to satisfy the
- ** space request. */
- addr = hdr+1;
- while( (pc = get2byte(&data[addr]))>0 ){
- size = get2byte(&data[pc+2]);
- if( size>=nByte ){
- if( size<nByte+4 ){
- memcpy(&data[addr], &data[pc], 2);
- data[hdr+7] = nFrag + size - nByte;
- return pc;
- }else{
- put2byte(&data[pc+2], size-nByte);
- return pc + size - nByte;
- }
- }
- addr = pc;
- }
- }
-
- /* Allocate memory from the gap in between the cell pointer array
- ** and the cell content area.
- */
- top = get2byte(&data[hdr+5]);
- nCell = get2byte(&data[hdr+3]);
- cellOffset = pPage->cellOffset;
- if( nFrag>=60 || cellOffset + 2*nCell > top - nByte ){
- if( defragmentPage(pPage) ) return 0;
- top = get2byte(&data[hdr+5]);
- }
- top -= nByte;
- assert( cellOffset + 2*nCell <= top );
- put2byte(&data[hdr+5], top);
- return top;
-}
-
-/*
-** Return a section of the pPage->aData to the freelist.
-** The first byte of the new free block is pPage->aDisk[start]
-** and the size of the block is "size" bytes.
-**
-** Most of the effort here is involved in coalesing adjacent
-** free blocks into a single big free block.
-*/
-static void freeSpace(MemPage *pPage, int start, int size){
- int addr, pbegin, hdr;
- unsigned char *data = pPage->aData;
-
- assert( pPage->pBt!=0 );
- assert( sqlite3pager_iswriteable(data) );
- assert( start>=pPage->hdrOffset+6+(pPage->leaf?0:4) );
- assert( (start + size)<=pPage->pBt->usableSize );
- if( size<4 ) size = 4;
-
- /* Add the space back into the linked list of freeblocks */
- hdr = pPage->hdrOffset;
- addr = hdr + 1;
- while( (pbegin = get2byte(&data[addr]))<start && pbegin>0 ){
- assert( pbegin<=pPage->pBt->usableSize-4 );
- assert( pbegin>addr );
- addr = pbegin;
- }
- assert( pbegin<=pPage->pBt->usableSize-4 );
- assert( pbegin>addr || pbegin==0 );
- put2byte(&data[addr], start);
- put2byte(&data[start], pbegin);
- put2byte(&data[start+2], size);
- pPage->nFree += size;
-
- /* Coalesce adjacent free blocks */
- addr = pPage->hdrOffset + 1;
- while( (pbegin = get2byte(&data[addr]))>0 ){
- int pnext, psize;
- assert( pbegin>addr );
- assert( pbegin<=pPage->pBt->usableSize-4 );
- pnext = get2byte(&data[pbegin]);
- psize = get2byte(&data[pbegin+2]);
- if( pbegin + psize + 3 >= pnext && pnext>0 ){
- int frag = pnext - (pbegin+psize);
- assert( frag<=data[pPage->hdrOffset+7] );
- data[pPage->hdrOffset+7] -= frag;
- put2byte(&data[pbegin], get2byte(&data[pnext]));
- put2byte(&data[pbegin+2], pnext+get2byte(&data[pnext+2])-pbegin);
- }else{
- addr = pbegin;
- }
- }
-
- /* If the cell content area begins with a freeblock, remove it. */
- if( data[hdr+1]==data[hdr+5] && data[hdr+2]==data[hdr+6] ){
- int top;
- pbegin = get2byte(&data[hdr+1]);
- memcpy(&data[hdr+1], &data[pbegin], 2);
- top = get2byte(&data[hdr+5]);
- put2byte(&data[hdr+5], top + get2byte(&data[pbegin+2]));
- }
-}
-
-/*
-** Decode the flags byte (the first byte of the header) for a page
-** and initialize fields of the MemPage structure accordingly.
-*/
-static void decodeFlags(MemPage *pPage, int flagByte){
- Btree *pBt; /* A copy of pPage->pBt */
-
- assert( pPage->hdrOffset==(pPage->pgno==1 ? 100 : 0) );
- pPage->intKey = (flagByte & (PTF_INTKEY|PTF_LEAFDATA))!=0;
- pPage->zeroData = (flagByte & PTF_ZERODATA)!=0;
- pPage->leaf = (flagByte & PTF_LEAF)!=0;
- pPage->childPtrSize = 4*(pPage->leaf==0);
- pBt = pPage->pBt;
- if( flagByte & PTF_LEAFDATA ){
- pPage->leafData = 1;
- pPage->maxLocal = pBt->maxLeaf;
- pPage->minLocal = pBt->minLeaf;
- }else{
- pPage->leafData = 0;
- pPage->maxLocal = pBt->maxLocal;
- pPage->minLocal = pBt->minLocal;
- }
- pPage->hasData = !(pPage->zeroData || (!pPage->leaf && pPage->leafData));
-}
-
-/*
-** Initialize the auxiliary information for a disk block.
-**
-** The pParent parameter must be a pointer to the MemPage which
-** is the parent of the page being initialized. The root of a
-** BTree has no parent and so for that page, pParent==NULL.
-**
-** Return SQLITE_OK on success. If we see that the page does
-** not contain a well-formed database page, then return
-** SQLITE_CORRUPT. Note that a return of SQLITE_OK does not
-** guarantee that the page is well-formed. It only shows that
-** we failed to detect any corruption.
-*/
-static int initPage(
- MemPage *pPage, /* The page to be initialized */
- MemPage *pParent /* The parent. Might be NULL */
-){
- int pc; /* Address of a freeblock within pPage->aData[] */
- int i; /* Loop counter */
- int hdr; /* Offset to beginning of page header */
- u8 *data; /* Equal to pPage->aData */
- Btree *pBt; /* The main btree structure */
- int usableSize; /* Amount of usable space on each page */
- int cellOffset; /* Offset from start of page to first cell pointer */
- int nFree; /* Number of unused bytes on the page */
- int top; /* First byte of the cell content area */
-
- pBt = pPage->pBt;
- assert( pBt!=0 );
- assert( pParent==0 || pParent->pBt==pBt );
- assert( pPage->pgno==sqlite3pager_pagenumber(pPage->aData) );
- assert( pPage->aData == &((unsigned char*)pPage)[-pBt->pageSize] );
- if( pPage->pParent!=pParent && (pPage->pParent!=0 || pPage->isInit) ){
- /* The parent page should never change unless the file is corrupt */
- return SQLITE_CORRUPT; /* bkpt-CORRUPT */
- }
- if( pPage->isInit ) return SQLITE_OK;
- if( pPage->pParent==0 && pParent!=0 ){
- pPage->pParent = pParent;
- sqlite3pager_ref(pParent->aData);
- }
- hdr = pPage->hdrOffset;
- data = pPage->aData;
- decodeFlags(pPage, data[hdr]);
- pPage->nOverflow = 0;
- pPage->idxShift = 0;
- usableSize = pBt->usableSize;
- pPage->cellOffset = cellOffset = hdr + 12 - 4*pPage->leaf;
- top = get2byte(&data[hdr+5]);
- pPage->nCell = get2byte(&data[hdr+3]);
- if( pPage->nCell>MX_CELL(pBt) ){
- /* To many cells for a single page. The page must be corrupt */
- return SQLITE_CORRUPT; /* bkpt-CORRUPT */
- }
- if( pPage->nCell==0 && pParent!=0 && pParent->pgno!=1 ){
- /* All pages must have at least one cell, except for root pages */
- return SQLITE_CORRUPT; /* bkpt-CORRUPT */
- }
-
- /* Compute the total free space on the page */
- pc = get2byte(&data[hdr+1]);
- nFree = data[hdr+7] + top - (cellOffset + 2*pPage->nCell);
- i = 0;
- while( pc>0 ){
- int next, size;
- if( pc>usableSize-4 ){
- /* Free block is off the page */
- return SQLITE_CORRUPT; /* bkpt-CORRUPT */
- }
- if( i++>SQLITE_MAX_PAGE_SIZE/4 ){
- /* The free block list forms an infinite loop */
- return SQLITE_CORRUPT; /* bkpt-CORRUPT */
- }
- next = get2byte(&data[pc]);
- size = get2byte(&data[pc+2]);
- if( next>0 && next<=pc+size+3 ){
- /* Free blocks must be in accending order */
- return SQLITE_CORRUPT; /* bkpt-CORRUPT */
- }
- nFree += size;
- pc = next;
- }
- pPage->nFree = nFree;
- if( nFree>=usableSize ){
- /* Free space cannot exceed total page size */
- return SQLITE_CORRUPT; /* bkpt-CORRUPT */
- }
-
- pPage->isInit = 1;
- pageIntegrity(pPage);
- return SQLITE_OK;
-}
-
-/*
-** Set up a raw page so that it looks like a database page holding
-** no entries.
-*/
-static void zeroPage(MemPage *pPage, int flags){
- unsigned char *data = pPage->aData;
- Btree *pBt = pPage->pBt;
- int hdr = pPage->hdrOffset;
- int first;
-
- assert( sqlite3pager_pagenumber(data)==pPage->pgno );
- assert( &data[pBt->pageSize] == (unsigned char*)pPage );
- assert( sqlite3pager_iswriteable(data) );
- memset(&data[hdr], 0, pBt->usableSize - hdr);
- data[hdr] = flags;
- first = hdr + 8 + 4*((flags&PTF_LEAF)==0);
- memset(&data[hdr+1], 0, 4);
- data[hdr+7] = 0;
- put2byte(&data[hdr+5], pBt->usableSize);
- pPage->nFree = pBt->usableSize - first;
- decodeFlags(pPage, flags);
- pPage->hdrOffset = hdr;
- pPage->cellOffset = first;
- pPage->nOverflow = 0;
- pPage->idxShift = 0;
- pPage->nCell = 0;
- pPage->isInit = 1;
- pageIntegrity(pPage);
-}
-
-/*
-** Get a page from the pager. Initialize the MemPage.pBt and
-** MemPage.aData elements if needed.
-*/
-static int getPage(Btree *pBt, Pgno pgno, MemPage **ppPage){
- int rc;
- unsigned char *aData;
- MemPage *pPage;
- rc = sqlite3pager_get(pBt->pPager, pgno, (void**)&aData);
- if( rc ) return rc;
- pPage = (MemPage*)&aData[pBt->pageSize];
- pPage->aData = aData;
- pPage->pBt = pBt;
- pPage->pgno = pgno;
- pPage->hdrOffset = pPage->pgno==1 ? 100 : 0;
- *ppPage = pPage;
- return SQLITE_OK;
-}
-
-/*
-** Get a page from the pager and initialize it. This routine
-** is just a convenience wrapper around separate calls to
-** getPage() and initPage().
-*/
-static int getAndInitPage(
- Btree *pBt, /* The database file */
- Pgno pgno, /* Number of the page to get */
- MemPage **ppPage, /* Write the page pointer here */
- MemPage *pParent /* Parent of the page */
-){
- int rc;
- if( pgno==0 ){
- return SQLITE_CORRUPT; /* bkpt-CORRUPT */
- }
- rc = getPage(pBt, pgno, ppPage);
- if( rc==SQLITE_OK && (*ppPage)->isInit==0 ){
- rc = initPage(*ppPage, pParent);
- }
- return rc;
-}
-
-/*
-** Release a MemPage. This should be called once for each prior
-** call to getPage.
-*/
-static void releasePage(MemPage *pPage){
- if( pPage ){
- assert( pPage->aData );
- assert( pPage->pBt );
- assert( &pPage->aData[pPage->pBt->pageSize]==(unsigned char*)pPage );
- sqlite3pager_unref(pPage->aData);
- }
-}
-
-/*
-** This routine is called when the reference count for a page
-** reaches zero. We need to unref the pParent pointer when that
-** happens.
-*/
-static void pageDestructor(void *pData, int pageSize){
- MemPage *pPage = (MemPage*)&((char*)pData)[pageSize];
- if( pPage->pParent ){
- MemPage *pParent = pPage->pParent;
- pPage->pParent = 0;
- releasePage(pParent);
- }
- pPage->isInit = 0;
-}
-
-/*
-** During a rollback, when the pager reloads information into the cache
-** so that the cache is restored to its original state at the start of
-** the transaction, for each page restored this routine is called.
-**
-** This routine needs to reset the extra data section at the end of the
-** page to agree with the restored data.
-*/
-static void pageReinit(void *pData, int pageSize){
- MemPage *pPage = (MemPage*)&((char*)pData)[pageSize];
- if( pPage->isInit ){
- pPage->isInit = 0;
- initPage(pPage, pPage->pParent);
- }
-}
-
-/*
-** Open a database file.
-**
-** zFilename is the name of the database file. If zFilename is NULL
-** a new database with a random name is created. This randomly named
-** database file will be deleted when sqlite3BtreeClose() is called.
-*/
-int sqlite3BtreeOpen(
- const char *zFilename, /* Name of the file containing the BTree database */
- Btree **ppBtree, /* Pointer to new Btree object written here */
- int flags /* Options */
-){
- Btree *pBt;
- int rc;
- int nReserve;
- unsigned char zDbHeader[100];
-
- /*
- ** The following asserts make sure that structures used by the btree are
- ** the right size. This is to guard against size changes that result
- ** when compiling on a different architecture.
- */
- assert( sizeof(i64)==8 );
- assert( sizeof(u64)==8 );
- assert( sizeof(u32)==4 );
- assert( sizeof(u16)==2 );
- assert( sizeof(Pgno)==4 );
- assert( sizeof(ptr)==sizeof(char*) );
- assert( sizeof(uptr)==sizeof(ptr) );
-
- pBt = sqliteMalloc( sizeof(*pBt) );
- if( pBt==0 ){
- *ppBtree = 0;
- return SQLITE_NOMEM;
- }
- rc = sqlite3pager_open(&pBt->pPager, zFilename, EXTRA_SIZE,
- (flags & BTREE_OMIT_JOURNAL)==0);
- if( rc!=SQLITE_OK ){
- if( pBt->pPager ) sqlite3pager_close(pBt->pPager);
- sqliteFree(pBt);
- *ppBtree = 0;
- return rc;
- }
- sqlite3pager_set_destructor(pBt->pPager, pageDestructor);
- sqlite3pager_set_reiniter(pBt->pPager, pageReinit);
- pBt->pCursor = 0;
- pBt->pPage1 = 0;
- pBt->readOnly = sqlite3pager_isreadonly(pBt->pPager);
- sqlite3pager_read_fileheader(pBt->pPager, sizeof(zDbHeader), zDbHeader);
- pBt->pageSize = get2byte(&zDbHeader[16]);
- if( pBt->pageSize<512 || pBt->pageSize>SQLITE_MAX_PAGE_SIZE ){
- pBt->pageSize = SQLITE_DEFAULT_PAGE_SIZE;
- pBt->maxEmbedFrac = 64; /* 25% */
- pBt->minEmbedFrac = 32; /* 12.5% */
- pBt->minLeafFrac = 32; /* 12.5% */
- nReserve = 0;
- }else{
- nReserve = zDbHeader[20];
- pBt->maxEmbedFrac = zDbHeader[21];
- pBt->minEmbedFrac = zDbHeader[22];
- pBt->minLeafFrac = zDbHeader[23];
- pBt->pageSizeFixed = 1;
- }
- pBt->usableSize = pBt->pageSize - nReserve;
- sqlite3pager_set_pagesize(pBt->pPager, pBt->pageSize);
- *ppBtree = pBt;
- return SQLITE_OK;
-}
-
-/*
-** Close an open database and invalidate all cursors.
-*/
-int sqlite3BtreeClose(Btree *pBt){
- while( pBt->pCursor ){
- sqlite3BtreeCloseCursor(pBt->pCursor);
- }
- sqlite3pager_close(pBt->pPager);
- sqliteFree(pBt);
- return SQLITE_OK;
-}
-
-/*
-** Change the busy handler callback function.
-*/
-int sqlite3BtreeSetBusyHandler(Btree *pBt, BusyHandler *pHandler){
- sqlite3pager_set_busyhandler(pBt->pPager, pHandler);
- return SQLITE_OK;
-}
-
-/*
-** Change the limit on the number of pages allowed in the cache.
-**
-** The maximum number of cache pages is set to the absolute
-** value of mxPage. If mxPage is negative, the pager will
-** operate asynchronously - it will not stop to do fsync()s
-** to insure data is written to the disk surface before
-** continuing. Transactions still work if synchronous is off,
-** and the database cannot be corrupted if this program
-** crashes. But if the operating system crashes or there is
-** an abrupt power failure when synchronous is off, the database
-** could be left in an inconsistent and unrecoverable state.
-** Synchronous is on by default so database corruption is not
-** normally a worry.
-*/
-int sqlite3BtreeSetCacheSize(Btree *pBt, int mxPage){
- sqlite3pager_set_cachesize(pBt->pPager, mxPage);
- return SQLITE_OK;
-}
-
-/*
-** Change the way data is synced to disk in order to increase or decrease
-** how well the database resists damage due to OS crashes and power
-** failures. Level 1 is the same as asynchronous (no syncs() occur and
-** there is a high probability of damage) Level 2 is the default. There
-** is a very low but non-zero probability of damage. Level 3 reduces the
-** probability of damage to near zero but with a write performance reduction.
-*/
-int sqlite3BtreeSetSafetyLevel(Btree *pBt, int level){
- sqlite3pager_set_safety_level(pBt->pPager, level);
- return SQLITE_OK;
-}
-
-/*
-** Change the default pages size and the number of reserved bytes per page.
-*/
-int sqlite3BtreeSetPageSize(Btree *pBt, int pageSize, int nReserve){
- if( pBt->pageSizeFixed ){
- return SQLITE_READONLY;
- }
- if( nReserve<0 ){
- nReserve = pBt->pageSize - pBt->usableSize;
- }
- if( pageSize>=512 && pageSize<=SQLITE_MAX_PAGE_SIZE ){
- pBt->pageSize = pageSize;
- sqlite3pager_set_pagesize(pBt->pPager, pageSize);
- }
- pBt->usableSize = pBt->pageSize - nReserve;
- return SQLITE_OK;
-}
-
-/*
-** Return the currently defined page size
-*/
-int sqlite3BtreeGetPageSize(Btree *pBt){
- return pBt->pageSize;
-}
-int sqlite3BtreeGetReserve(Btree *pBt){
- return pBt->pageSize - pBt->usableSize;
-}
-
-/*
-** Get a reference to pPage1 of the database file. This will
-** also acquire a readlock on that file.
-**
-** SQLITE_OK is returned on success. If the file is not a
-** well-formed database file, then SQLITE_CORRUPT is returned.
-** SQLITE_BUSY is returned if the database is locked. SQLITE_NOMEM
-** is returned if we run out of memory. SQLITE_PROTOCOL is returned
-** if there is a locking protocol violation.
-*/
-static int lockBtree(Btree *pBt){
- int rc;
- MemPage *pPage1;
- if( pBt->pPage1 ) return SQLITE_OK;
- rc = getPage(pBt, 1, &pPage1);
- if( rc!=SQLITE_OK ) return rc;
-
-
- /* Do some checking to help insure the file we opened really is
- ** a valid database file.
- */
- rc = SQLITE_NOTADB;
- if( sqlite3pager_pagecount(pBt->pPager)>0 ){
- u8 *page1 = pPage1->aData;
- if( memcmp(page1, zMagicHeader, 16)!=0 ){
- goto page1_init_failed;
- }
- if( page1[18]>1 || page1[19]>1 ){
- goto page1_init_failed;
- }
- pBt->pageSize = get2byte(&page1[16]);
- pBt->usableSize = pBt->pageSize - page1[20];
- if( pBt->usableSize<500 ){
- goto page1_init_failed;
- }
- pBt->maxEmbedFrac = page1[21];
- pBt->minEmbedFrac = page1[22];
- pBt->minLeafFrac = page1[23];
- }
-
- /* maxLocal is the maximum amount of payload to store locally for
- ** a cell. Make sure it is small enough so that at least minFanout
- ** cells can will fit on one page. We assume a 10-byte page header.
- ** Besides the payload, the cell must store:
- ** 2-byte pointer to the cell
- ** 4-byte child pointer
- ** 9-byte nKey value
- ** 4-byte nData value
- ** 4-byte overflow page pointer
- ** So a cell consists of a 2-byte poiner, a header which is as much as
- ** 17 bytes long, 0 to N bytes of payload, and an optional 4 byte overflow
- ** page pointer.
- */
- pBt->maxLocal = (pBt->usableSize-12)*pBt->maxEmbedFrac/255 - 23;
- pBt->minLocal = (pBt->usableSize-12)*pBt->minEmbedFrac/255 - 23;
- pBt->maxLeaf = pBt->usableSize - 35;
- pBt->minLeaf = (pBt->usableSize-12)*pBt->minLeafFrac/255 - 23;
- if( pBt->minLocal>pBt->maxLocal || pBt->maxLocal<0 ){
- goto page1_init_failed;
- }
- assert( pBt->maxLeaf + 23 <= MX_CELL_SIZE(pBt) );
- pBt->pPage1 = pPage1;
- return SQLITE_OK;
-
-page1_init_failed:
- releasePage(pPage1);
- pBt->pPage1 = 0;
- return rc;
-}
-
-/*
-** If there are no outstanding cursors and we are not in the middle
-** of a transaction but there is a read lock on the database, then
-** this routine unrefs the first page of the database file which
-** has the effect of releasing the read lock.
-**
-** If there are any outstanding cursors, this routine is a no-op.
-**
-** If there is a transaction in progress, this routine is a no-op.
-*/
-static void unlockBtreeIfUnused(Btree *pBt){
- if( pBt->inTrans==TRANS_NONE && pBt->pCursor==0 && pBt->pPage1!=0 ){
- if( pBt->pPage1->aData==0 ){
- MemPage *pPage = pBt->pPage1;
- pPage->aData = &((char*)pPage)[-pBt->pageSize];
- pPage->pBt = pBt;
- pPage->pgno = 1;
- }
- releasePage(pBt->pPage1);
- pBt->pPage1 = 0;
- pBt->inStmt = 0;
- }
-}
-
-/*
-** Create a new database by initializing the first page of the
-** file.
-*/
-static int newDatabase(Btree *pBt){
- MemPage *pP1;
- unsigned char *data;
- int rc;
- if( sqlite3pager_pagecount(pBt->pPager)>0 ) return SQLITE_OK;
- pP1 = pBt->pPage1;
- assert( pP1!=0 );
- data = pP1->aData;
- rc = sqlite3pager_write(data);
- if( rc ) return rc;
- memcpy(data, zMagicHeader, sizeof(zMagicHeader));
- assert( sizeof(zMagicHeader)==16 );
- put2byte(&data[16], pBt->pageSize);
- data[18] = 1;
- data[19] = 1;
- data[20] = pBt->pageSize - pBt->usableSize;
- data[21] = pBt->maxEmbedFrac;
- data[22] = pBt->minEmbedFrac;
- data[23] = pBt->minLeafFrac;
- memset(&data[24], 0, 100-24);
- zeroPage(pP1, PTF_INTKEY|PTF_LEAF|PTF_LEAFDATA );
- pBt->pageSizeFixed = 1;
- return SQLITE_OK;
-}
-
-/*
-** Attempt to start a new transaction. A write-transaction
-** is started if the second argument is nonzero, otherwise a read-
-** transaction. If the second argument is 2 or more and exclusive
-** transaction is started, meaning that no other process is allowed
-** to access the database. A preexisting transaction may not be
-** upgrade to exclusive by calling this routine a second time - the
-** exclusivity flag only works for a new transaction.
-**
-** A write-transaction must be started before attempting any
-** changes to the database. None of the following routines
-** will work unless a transaction is started first:
-**
-** sqlite3BtreeCreateTable()
-** sqlite3BtreeCreateIndex()
-** sqlite3BtreeClearTable()
-** sqlite3BtreeDropTable()
-** sqlite3BtreeInsert()
-** sqlite3BtreeDelete()
-** sqlite3BtreeUpdateMeta()
-**
-** If wrflag is true, then nMaster specifies the maximum length of
-** a master journal file name supplied later via sqlite3BtreeSync().
-** This is so that appropriate space can be allocated in the journal file
-** when it is created..
-*/
-int sqlite3BtreeBeginTrans(Btree *pBt, int wrflag){
- int rc = SQLITE_OK;
-
- /* If the btree is already in a write-transaction, or it
- ** is already in a read-transaction and a read-transaction
- ** is requested, this is a no-op.
- */
- if( pBt->inTrans==TRANS_WRITE ||
- (pBt->inTrans==TRANS_READ && !wrflag) ){
- return SQLITE_OK;
- }
- if( pBt->readOnly && wrflag ){
- return SQLITE_READONLY;
- }
-
- if( pBt->pPage1==0 ){
- rc = lockBtree(pBt);
- }
-
- if( rc==SQLITE_OK && wrflag ){
- rc = sqlite3pager_begin(pBt->pPage1->aData, wrflag>1);
- if( rc==SQLITE_OK ){
- rc = newDatabase(pBt);
- }
- }
-
- if( rc==SQLITE_OK ){
- pBt->inTrans = (wrflag?TRANS_WRITE:TRANS_READ);
- if( wrflag ) pBt->inStmt = 0;
- }else{
- unlockBtreeIfUnused(pBt);
- }
- return rc;
-}
-
-/*
-** Commit the transaction currently in progress.
-**
-** This will release the write lock on the database file. If there
-** are no active cursors, it also releases the read lock.
-*/
-int sqlite3BtreeCommit(Btree *pBt){
- int rc = SQLITE_OK;
- if( pBt->inTrans==TRANS_WRITE ){
- rc = sqlite3pager_commit(pBt->pPager);
- }
- pBt->inTrans = TRANS_NONE;
- pBt->inStmt = 0;
- unlockBtreeIfUnused(pBt);
- return rc;
-}
-
-#ifndef NDEBUG
-/*
-** Return the number of write-cursors open on this handle. This is for use
-** in assert() expressions, so it is only compiled if NDEBUG is not
-** defined.
-*/
-static int countWriteCursors(Btree *pBt){
- BtCursor *pCur;
- int r = 0;
- for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
- if( pCur->wrFlag ) r++;
- }
- return r;
-}
-#endif
-
-#if 0
-/*
-** Invalidate all cursors
-*/
-static void invalidateCursors(Btree *pBt){
- BtCursor *pCur;
- for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
- MemPage *pPage = pCur->pPage;
- if( pPage /* && !pPage->isInit */ ){
- pageIntegrity(pPage);
- releasePage(pPage);
- pCur->pPage = 0;
- pCur->isValid = 0;
- pCur->status = SQLITE_ABORT;
- }
- }
-}
-#endif
-
-#ifdef SQLITE_TEST
-/*
-** Print debugging information about all cursors to standard output.
-*/
-void sqlite3BtreeCursorList(Btree *pBt){
- BtCursor *pCur;
- for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
- MemPage *pPage = pCur->pPage;
- char *zMode = pCur->wrFlag ? "rw" : "ro";
- sqlite3DebugPrintf("CURSOR %p rooted at %4d(%s) currently at %d.%d%s\n",
- pCur, pCur->pgnoRoot, zMode,
- pPage ? pPage->pgno : 0, pCur->idx,
- pCur->isValid ? "" : " eof"
- );
- }
-}
-#endif
-
-/*
-** Rollback the transaction in progress. All cursors will be
-** invalided by this operation. Any attempt to use a cursor
-** that was open at the beginning of this operation will result
-** in an error.
-**
-** This will release the write lock on the database file. If there
-** are no active cursors, it also releases the read lock.
-*/
-int sqlite3BtreeRollback(Btree *pBt){
- int rc = SQLITE_OK;
- MemPage *pPage1;
- if( pBt->inTrans==TRANS_WRITE ){
- rc = sqlite3pager_rollback(pBt->pPager);
- /* The rollback may have destroyed the pPage1->aData value. So
- ** call getPage() on page 1 again to make sure pPage1->aData is
- ** set correctly. */
- if( getPage(pBt, 1, &pPage1)==SQLITE_OK ){
- releasePage(pPage1);
- }
- assert( countWriteCursors(pBt)==0 );
- }
- pBt->inTrans = TRANS_NONE;
- pBt->inStmt = 0;
- unlockBtreeIfUnused(pBt);
- return rc;
-}
-
-/*
-** Start a statement subtransaction. The subtransaction can
-** can be rolled back independently of the main transaction.
-** You must start a transaction before starting a subtransaction.
-** The subtransaction is ended automatically if the main transaction
-** commits or rolls back.
-**
-** Only one subtransaction may be active at a time. It is an error to try
-** to start a new subtransaction if another subtransaction is already active.
-**
-** Statement subtransactions are used around individual SQL statements
-** that are contained within a BEGIN...COMMIT block. If a constraint
-** error occurs within the statement, the effect of that one statement
-** can be rolled back without having to rollback the entire transaction.
-*/
-int sqlite3BtreeBeginStmt(Btree *pBt){
- int rc;
- if( (pBt->inTrans!=TRANS_WRITE) || pBt->inStmt ){
- return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
- }
- rc = pBt->readOnly ? SQLITE_OK : sqlite3pager_stmt_begin(pBt->pPager);
- pBt->inStmt = 1;
- return rc;
-}
-
-
-/*
-** Commit the statment subtransaction currently in progress. If no
-** subtransaction is active, this is a no-op.
-*/
-int sqlite3BtreeCommitStmt(Btree *pBt){
- int rc;
- if( pBt->inStmt && !pBt->readOnly ){
- rc = sqlite3pager_stmt_commit(pBt->pPager);
- }else{
- rc = SQLITE_OK;
- }
- pBt->inStmt = 0;
- return rc;
-}
-
-/*
-** Rollback the active statement subtransaction. If no subtransaction
-** is active this routine is a no-op.
-**
-** All cursors will be invalidated by this operation. Any attempt
-** to use a cursor that was open at the beginning of this operation
-** will result in an error.
-*/
-int sqlite3BtreeRollbackStmt(Btree *pBt){
- int rc;
- if( pBt->inStmt==0 || pBt->readOnly ) return SQLITE_OK;
- rc = sqlite3pager_stmt_rollback(pBt->pPager);
- assert( countWriteCursors(pBt)==0 );
- pBt->inStmt = 0;
- return rc;
-}
-
-/*
-** Default key comparison function to be used if no comparison function
-** is specified on the sqlite3BtreeCursor() call.
-*/
-static int dfltCompare(
- void *NotUsed, /* User data is not used */
- int n1, const void *p1, /* First key to compare */
- int n2, const void *p2 /* Second key to compare */
-){
- int c;
- c = memcmp(p1, p2, n1<n2 ? n1 : n2);
- if( c==0 ){
- c = n1 - n2;
- }
- return c;
-}
-
-/*
-** Create a new cursor for the BTree whose root is on the page
-** iTable. The act of acquiring a cursor gets a read lock on
-** the database file.
-**
-** If wrFlag==0, then the cursor can only be used for reading.
-** If wrFlag==1, then the cursor can be used for reading or for
-** writing if other conditions for writing are also met. These
-** are the conditions that must be met in order for writing to
-** be allowed:
-**
-** 1: The cursor must have been opened with wrFlag==1
-**
-** 2: No other cursors may be open with wrFlag==0 on the same table
-**
-** 3: The database must be writable (not on read-only media)
-**
-** 4: There must be an active transaction.
-**
-** Condition 2 warrants further discussion. If any cursor is opened
-** on a table with wrFlag==0, that prevents all other cursors from
-** writing to that table. This is a kind of "read-lock". When a cursor
-** is opened with wrFlag==0 it is guaranteed that the table will not
-** change as long as the cursor is open. This allows the cursor to
-** do a sequential scan of the table without having to worry about
-** entries being inserted or deleted during the scan. Cursors should
-** be opened with wrFlag==0 only if this read-lock property is needed.
-** That is to say, cursors should be opened with wrFlag==0 only if they
-** intend to use the sqlite3BtreeNext() system call. All other cursors
-** should be opened with wrFlag==1 even if they never really intend
-** to write.
-**
-** No checking is done to make sure that page iTable really is the
-** root page of a b-tree. If it is not, then the cursor acquired
-** will not work correctly.
-**
-** The comparison function must be logically the same for every cursor
-** on a particular table. Changing the comparison function will result
-** in incorrect operations. If the comparison function is NULL, a
-** default comparison function is used. The comparison function is
-** always ignored for INTKEY tables.
-*/
-int sqlite3BtreeCursor(
- Btree *pBt, /* The btree */
- int iTable, /* Root page of table to open */
- int wrFlag, /* 1 to write. 0 read-only */
- int (*xCmp)(void*,int,const void*,int,const void*), /* Key Comparison func */
- void *pArg, /* First arg to xCompare() */
- BtCursor **ppCur /* Write new cursor here */
-){
- int rc;
- BtCursor *pCur;
-
- *ppCur = 0;
- if( wrFlag ){
- if( pBt->readOnly ){
- return SQLITE_READONLY;
- }
- if( checkReadLocks(pBt, iTable, 0) ){
- return SQLITE_LOCKED;
- }
- }
- if( pBt->pPage1==0 ){
- rc = lockBtree(pBt);
- if( rc!=SQLITE_OK ){
- return rc;
- }
- }
- pCur = sqliteMallocRaw( sizeof(*pCur) );
- if( pCur==0 ){
- rc = SQLITE_NOMEM;
- goto create_cursor_exception;
- }
- pCur->pgnoRoot = (Pgno)iTable;
- if( iTable==1 && sqlite3pager_pagecount(pBt->pPager)==0 ){
- rc = SQLITE_EMPTY;
- pCur->pPage = 0;
- goto create_cursor_exception;
- }
- pCur->pPage = 0; /* For exit-handler, in case getAndInitPage() fails. */
- rc = getAndInitPage(pBt, pCur->pgnoRoot, &pCur->pPage, 0);
- if( rc!=SQLITE_OK ){
- goto create_cursor_exception;
- }
- pCur->xCompare = xCmp ? xCmp : dfltCompare;
- pCur->pArg = pArg;
- pCur->pBt = pBt;
- pCur->wrFlag = wrFlag;
- pCur->idx = 0;
- memset(&pCur->info, 0, sizeof(pCur->info));
- pCur->pNext = pBt->pCursor;
- if( pCur->pNext ){
- pCur->pNext->pPrev = pCur;
- }
- pCur->pPrev = 0;
- pBt->pCursor = pCur;
- pCur->isValid = 0;
- pCur->status = SQLITE_OK;
- *ppCur = pCur;
- return SQLITE_OK;
-
-create_cursor_exception:
- if( pCur ){
- releasePage(pCur->pPage);
- sqliteFree(pCur);
- }
- unlockBtreeIfUnused(pBt);
- return rc;
-}
-
-#if 0 /* Not Used */
-/*
-** Change the value of the comparison function used by a cursor.
-*/
-void sqlite3BtreeSetCompare(
- BtCursor *pCur, /* The cursor to whose comparison function is changed */
- int(*xCmp)(void*,int,const void*,int,const void*), /* New comparison func */
- void *pArg /* First argument to xCmp() */
-){
- pCur->xCompare = xCmp ? xCmp : dfltCompare;
- pCur->pArg = pArg;
-}
-#endif
-
-/*
-** Close a cursor. The read lock on the database file is released
-** when the last cursor is closed.
-*/
-int sqlite3BtreeCloseCursor(BtCursor *pCur){
- Btree *pBt = pCur->pBt;
- if( pCur->pPrev ){
- pCur->pPrev->pNext = pCur->pNext;
- }else{
- pBt->pCursor = pCur->pNext;
- }
- if( pCur->pNext ){
- pCur->pNext->pPrev = pCur->pPrev;
- }
- releasePage(pCur->pPage);
- unlockBtreeIfUnused(pBt);
- sqliteFree(pCur);
- return SQLITE_OK;
-}
-
-/*
-** Make a temporary cursor by filling in the fields of pTempCur.
-** The temporary cursor is not on the cursor list for the Btree.
-*/
-static void getTempCursor(BtCursor *pCur, BtCursor *pTempCur){
- memcpy(pTempCur, pCur, sizeof(*pCur));
- pTempCur->pNext = 0;
- pTempCur->pPrev = 0;
- if( pTempCur->pPage ){
- sqlite3pager_ref(pTempCur->pPage->aData);
- }
-}
-
-/*
-** Delete a temporary cursor such as was made by the CreateTemporaryCursor()
-** function above.
-*/
-static void releaseTempCursor(BtCursor *pCur){
- if( pCur->pPage ){
- sqlite3pager_unref(pCur->pPage->aData);
- }
-}
-
-/*
-** Make sure the BtCursor.info field of the given cursor is valid.
-** If it is not already valid, call parseCell() to fill it in.
-**
-** BtCursor.info is a cache of the information in the current cell.
-** Using this cache reduces the number of calls to parseCell().
-*/
-static void getCellInfo(BtCursor *pCur){
- if( pCur->info.nSize==0 ){
- parseCell(pCur->pPage, pCur->idx, &pCur->info);
- }else{
-#ifndef NDEBUG
- CellInfo info;
- memset(&info, 0, sizeof(info));
- parseCell(pCur->pPage, pCur->idx, &info);
- assert( memcmp(&info, &pCur->info, sizeof(info))==0 );
-#endif
- }
-}
-
-/*
-** Set *pSize to the size of the buffer needed to hold the value of
-** the key for the current entry. If the cursor is not pointing
-** to a valid entry, *pSize is set to 0.
-**
-** For a table with the INTKEY flag set, this routine returns the key
-** itself, not the number of bytes in the key.
-*/
-int sqlite3BtreeKeySize(BtCursor *pCur, i64 *pSize){
- if( !pCur->isValid ){
- *pSize = 0;
- }else{
- getCellInfo(pCur);
- *pSize = pCur->info.nKey;
- }
- return SQLITE_OK;
-}
-
-/*
-** Set *pSize to the number of bytes of data in the entry the
-** cursor currently points to. Always return SQLITE_OK.
-** Failure is not possible. If the cursor is not currently
-** pointing to an entry (which can happen, for example, if
-** the database is empty) then *pSize is set to 0.
-*/
-int sqlite3BtreeDataSize(BtCursor *pCur, u32 *pSize){
- if( !pCur->isValid ){
- /* Not pointing at a valid entry - set *pSize to 0. */
- *pSize = 0;
- }else{
- getCellInfo(pCur);
- *pSize = pCur->info.nData;
- }
- return SQLITE_OK;
-}
-
-/*
-** Read payload information from the entry that the pCur cursor is
-** pointing to. Begin reading the payload at "offset" and read
-** a total of "amt" bytes. Put the result in zBuf.
-**
-** This routine does not make a distinction between key and data.
-** It just reads bytes from the payload area. Data might appear
-** on the main page or be scattered out on multiple overflow pages.
-*/
-static int getPayload(
- BtCursor *pCur, /* Cursor pointing to entry to read from */
- int offset, /* Begin reading this far into payload */
- int amt, /* Read this many bytes */
- unsigned char *pBuf, /* Write the bytes into this buffer */
- int skipKey /* offset begins at data if this is true */
-){
- unsigned char *aPayload;
- Pgno nextPage;
- int rc;
- MemPage *pPage;
- Btree *pBt;
- int ovflSize;
- u32 nKey;
-
- assert( pCur!=0 && pCur->pPage!=0 );
- assert( pCur->isValid );
- pBt = pCur->pBt;
- pPage = pCur->pPage;
- pageIntegrity(pPage);
- assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
- getCellInfo(pCur);
- aPayload = pCur->info.pCell;
- aPayload += pCur->info.nHeader;
- if( pPage->intKey ){
- nKey = 0;
- }else{
- nKey = pCur->info.nKey;
- }
- assert( offset>=0 );
- if( skipKey ){
- offset += nKey;
- }
- if( offset+amt > nKey+pCur->info.nData ){
- return SQLITE_ERROR;
- }
- if( offset<pCur->info.nLocal ){
- int a = amt;
- if( a+offset>pCur->info.nLocal ){
- a = pCur->info.nLocal - offset;
- }
- memcpy(pBuf, &aPayload[offset], a);
- if( a==amt ){
- return SQLITE_OK;
- }
- offset = 0;
- pBuf += a;
- amt -= a;
- }else{
- offset -= pCur->info.nLocal;
- }
- ovflSize = pBt->usableSize - 4;
- if( amt>0 ){
- nextPage = get4byte(&aPayload[pCur->info.nLocal]);
- while( amt>0 && nextPage ){
- rc = sqlite3pager_get(pBt->pPager, nextPage, (void**)&aPayload);
- if( rc!=0 ){
- return rc;
- }
- nextPage = get4byte(aPayload);
- if( offset<ovflSize ){
- int a = amt;
- if( a + offset > ovflSize ){
- a = ovflSize - offset;
- }
- memcpy(pBuf, &aPayload[offset+4], a);
- offset = 0;
- amt -= a;
- pBuf += a;
- }else{
- offset -= ovflSize;
- }
- sqlite3pager_unref(aPayload);
- }
- }
-
- if( amt>0 ){
- return SQLITE_CORRUPT; /* bkpt-CORRUPT */
- }
- return SQLITE_OK;
-}
-
-/*
-** Read part of the key associated with cursor pCur. Exactly
-** "amt" bytes will be transfered into pBuf[]. The transfer
-** begins at "offset".
-**
-** Return SQLITE_OK on success or an error code if anything goes
-** wrong. An error is returned if "offset+amt" is larger than
-** the available payload.
-*/
-int sqlite3BtreeKey(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){
- if( pCur->isValid==0 ){
- return pCur->status;
- }
- assert( pCur->pPage!=0 );
- assert( pCur->pPage->intKey==0 );
- assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
- return getPayload(pCur, offset, amt, (unsigned char*)pBuf, 0);
-}
-
-/*
-** Read part of the data associated with cursor pCur. Exactly
-** "amt" bytes will be transfered into pBuf[]. The transfer
-** begins at "offset".
-**
-** Return SQLITE_OK on success or an error code if anything goes
-** wrong. An error is returned if "offset+amt" is larger than
-** the available payload.
-*/
-int sqlite3BtreeData(BtCursor *pCur, u32 offset, u32 amt, void *pBuf){
- if( !pCur->isValid ){
- return pCur->status ? pCur->status : SQLITE_INTERNAL;
- }
- assert( pCur->pPage!=0 );
- assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
- return getPayload(pCur, offset, amt, pBuf, 1);
-}
-
-/*
-** Return a pointer to payload information from the entry that the
-** pCur cursor is pointing to. The pointer is to the beginning of
-** the key if skipKey==0 and it points to the beginning of data if
-** skipKey==1. The number of bytes of available key/data is written
-** into *pAmt. If *pAmt==0, then the value returned will not be
-** a valid pointer.
-**
-** This routine is an optimization. It is common for the entire key
-** and data to fit on the local page and for there to be no overflow
-** pages. When that is so, this routine can be used to access the
-** key and data without making a copy. If the key and/or data spills
-** onto overflow pages, then getPayload() must be used to reassembly
-** the key/data and copy it into a preallocated buffer.
-**
-** The pointer returned by this routine looks directly into the cached
-** page of the database. The data might change or move the next time
-** any btree routine is called.
-*/
-static const unsigned char *fetchPayload(
- BtCursor *pCur, /* Cursor pointing to entry to read from */
- int *pAmt, /* Write the number of available bytes here */
- int skipKey /* read beginning at data if this is true */
-){
- unsigned char *aPayload;
- MemPage *pPage;
- Btree *pBt;
- u32 nKey;
- int nLocal;
-
- assert( pCur!=0 && pCur->pPage!=0 );
- assert( pCur->isValid );
- pBt = pCur->pBt;
- pPage = pCur->pPage;
- pageIntegrity(pPage);
- assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
- getCellInfo(pCur);
- aPayload = pCur->info.pCell;
- aPayload += pCur->info.nHeader;
- if( pPage->intKey ){
- nKey = 0;
- }else{
- nKey = pCur->info.nKey;
- }
- if( skipKey ){
- aPayload += nKey;
- nLocal = pCur->info.nLocal - nKey;
- }else{
- nLocal = pCur->info.nLocal;
- if( nLocal>nKey ){
- nLocal = nKey;
- }
- }
- *pAmt = nLocal;
- return aPayload;
-}
-
-
-/*
-** For the entry that cursor pCur is point to, return as
-** many bytes of the key or data as are available on the local
-** b-tree page. Write the number of available bytes into *pAmt.
-**
-** The pointer returned is ephemeral. The key/data may move
-** or be destroyed on the next call to any Btree routine.
-**
-** These routines is used to get quick access to key and data
-** in the common case where no overflow pages are used.
-*/
-const void *sqlite3BtreeKeyFetch(BtCursor *pCur, int *pAmt){
- return (const void*)fetchPayload(pCur, pAmt, 0);
-}
-const void *sqlite3BtreeDataFetch(BtCursor *pCur, int *pAmt){
- return (const void*)fetchPayload(pCur, pAmt, 1);
-}
-
-
-/*
-** Move the cursor down to a new child page. The newPgno argument is the
-** page number of the child page to move to.
-*/
-static int moveToChild(BtCursor *pCur, u32 newPgno){
- int rc;
- MemPage *pNewPage;
- MemPage *pOldPage;
- Btree *pBt = pCur->pBt;
-
- assert( pCur->isValid );
- rc = getAndInitPage(pBt, newPgno, &pNewPage, pCur->pPage);
- if( rc ) return rc;
- pageIntegrity(pNewPage);
- pNewPage->idxParent = pCur->idx;
- pOldPage = pCur->pPage;
- pOldPage->idxShift = 0;
- releasePage(pOldPage);
- pCur->pPage = pNewPage;
- pCur->idx = 0;
- pCur->info.nSize = 0;
- if( pNewPage->nCell<1 ){
- return SQLITE_CORRUPT; /* bkpt-CORRUPT */
- }
- return SQLITE_OK;
-}
-
-/*
-** Return true if the page is the virtual root of its table.
-**
-** The virtual root page is the root page for most tables. But
-** for the table rooted on page 1, sometime the real root page
-** is empty except for the right-pointer. In such cases the
-** virtual root page is the page that the right-pointer of page
-** 1 is pointing to.
-*/
-static int isRootPage(MemPage *pPage){
- MemPage *pParent = pPage->pParent;
- if( pParent==0 ) return 1;
- if( pParent->pgno>1 ) return 0;
- if( get2byte(&pParent->aData[pParent->hdrOffset+3])==0 ) return 1;
- return 0;
-}
-
-/*
-** Move the cursor up to the parent page.
-**
-** pCur->idx is set to the cell index that contains the pointer
-** to the page we are coming from. If we are coming from the
-** right-most child page then pCur->idx is set to one more than
-** the largest cell index.
-*/
-static void moveToParent(BtCursor *pCur){
- Pgno oldPgno;
- MemPage *pParent;
- MemPage *pPage;
- int idxParent;
-
- assert( pCur->isValid );
- pPage = pCur->pPage;
- assert( pPage!=0 );
- assert( !isRootPage(pPage) );
- pageIntegrity(pPage);
- pParent = pPage->pParent;
- assert( pParent!=0 );
- pageIntegrity(pParent);
- idxParent = pPage->idxParent;
- sqlite3pager_ref(pParent->aData);
- oldPgno = pPage->pgno;
- releasePage(pPage);
- pCur->pPage = pParent;
- pCur->info.nSize = 0;
- assert( pParent->idxShift==0 );
- pCur->idx = idxParent;
-}
-
-/*
-** Move the cursor to the root page
-*/
-static int moveToRoot(BtCursor *pCur){
- MemPage *pRoot;
- int rc;
- Btree *pBt = pCur->pBt;
-
- rc = getAndInitPage(pBt, pCur->pgnoRoot, &pRoot, 0);
- if( rc ){
- pCur->isValid = 0;
- return rc;
- }
- releasePage(pCur->pPage);
- pageIntegrity(pRoot);
- pCur->pPage = pRoot;
- pCur->idx = 0;
- pCur->info.nSize = 0;
- if( pRoot->nCell==0 && !pRoot->leaf ){
- Pgno subpage;
- assert( pRoot->pgno==1 );
- subpage = get4byte(&pRoot->aData[pRoot->hdrOffset+8]);
- assert( subpage>0 );
- pCur->isValid = 1;
- rc = moveToChild(pCur, subpage);
- }
- pCur->isValid = pCur->pPage->nCell>0;
- return rc;
-}
-
-/*
-** Move the cursor down to the left-most leaf entry beneath the
-** entry to which it is currently pointing.
-*/
-static int moveToLeftmost(BtCursor *pCur){
- Pgno pgno;
- int rc;
- MemPage *pPage;
-
- assert( pCur->isValid );
- while( !(pPage = pCur->pPage)->leaf ){
- assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
- pgno = get4byte(findCell(pPage, pCur->idx));
- rc = moveToChild(pCur, pgno);
- if( rc ) return rc;
- }
- return SQLITE_OK;
-}
-
-/*
-** Move the cursor down to the right-most leaf entry beneath the
-** page to which it is currently pointing. Notice the difference
-** between moveToLeftmost() and moveToRightmost(). moveToLeftmost()
-** finds the left-most entry beneath the *entry* whereas moveToRightmost()
-** finds the right-most entry beneath the *page*.
-*/
-static int moveToRightmost(BtCursor *pCur){
- Pgno pgno;
- int rc;
- MemPage *pPage;
-
- assert( pCur->isValid );
- while( !(pPage = pCur->pPage)->leaf ){
- pgno = get4byte(&pPage->aData[pPage->hdrOffset+8]);
- pCur->idx = pPage->nCell;
- rc = moveToChild(pCur, pgno);
- if( rc ) return rc;
- }
- pCur->idx = pPage->nCell - 1;
- pCur->info.nSize = 0;
- return SQLITE_OK;
-}
-
-/* Move the cursor to the first entry in the table. Return SQLITE_OK
-** on success. Set *pRes to 0 if the cursor actually points to something
-** or set *pRes to 1 if the table is empty.
-*/
-int sqlite3BtreeFirst(BtCursor *pCur, int *pRes){
- int rc;
- if( pCur->status ){
- return pCur->status;
- }
- rc = moveToRoot(pCur);
- if( rc ) return rc;
- if( pCur->isValid==0 ){
- assert( pCur->pPage->nCell==0 );
- *pRes = 1;
- return SQLITE_OK;
- }
- assert( pCur->pPage->nCell>0 );
- *pRes = 0;
- rc = moveToLeftmost(pCur);
- return rc;
-}
-
-/* Move the cursor to the last entry in the table. Return SQLITE_OK
-** on success. Set *pRes to 0 if the cursor actually points to something
-** or set *pRes to 1 if the table is empty.
-*/
-int sqlite3BtreeLast(BtCursor *pCur, int *pRes){
- int rc;
- if( pCur->status ){
- return pCur->status;
- }
- rc = moveToRoot(pCur);
- if( rc ) return rc;
- if( pCur->isValid==0 ){
- assert( pCur->pPage->nCell==0 );
- *pRes = 1;
- return SQLITE_OK;
- }
- assert( pCur->isValid );
- *pRes = 0;
- rc = moveToRightmost(pCur);
- return rc;
-}
-
-/* Move the cursor so that it points to an entry near pKey/nKey.
-** Return a success code.
-**
-** For INTKEY tables, only the nKey parameter is used. pKey is
-** ignored. For other tables, nKey is the number of bytes of data
-** in nKey. The comparison function specified when the cursor was
-** created is used to compare keys.
-**
-** If an exact match is not found, then the cursor is always
-** left pointing at a leaf page which would hold the entry if it
-** were present. The cursor might point to an entry that comes
-** before or after the key.
-**
-** The result of comparing the key with the entry to which the
-** cursor is written to *pRes if pRes!=NULL. The meaning of
-** this value is as follows:
-**
-** *pRes<0 The cursor is left pointing at an entry that
-** is smaller than pKey or if the table is empty
-** and the cursor is therefore left point to nothing.
-**
-** *pRes==0 The cursor is left pointing at an entry that
-** exactly matches pKey.
-**
-** *pRes>0 The cursor is left pointing at an entry that
-** is larger than pKey.
-*/
-int sqlite3BtreeMoveto(BtCursor *pCur, const void *pKey, i64 nKey, int *pRes){
- int rc;
-
- if( pCur->status ){
- return pCur->status;
- }
- rc = moveToRoot(pCur);
- if( rc ) return rc;
- assert( pCur->pPage );
- assert( pCur->pPage->isInit );
- if( pCur->isValid==0 ){
- *pRes = -1;
- assert( pCur->pPage->nCell==0 );
- return SQLITE_OK;
- }
- for(;;){
- int lwr, upr;
- Pgno chldPg;
- MemPage *pPage = pCur->pPage;
- int c = -1; /* pRes return if table is empty must be -1 */
- lwr = 0;
- upr = pPage->nCell-1;
- pageIntegrity(pPage);
- while( lwr<=upr ){
- void *pCellKey;
- i64 nCellKey;
- pCur->idx = (lwr+upr)/2;
- pCur->info.nSize = 0;
- sqlite3BtreeKeySize(pCur, &nCellKey);
- if( pPage->intKey ){
- if( nCellKey<nKey ){
- c = -1;
- }else if( nCellKey>nKey ){
- c = +1;
- }else{
- c = 0;
- }
- }else{
- int available;
- pCellKey = (void *)fetchPayload(pCur, &available, 0);
- if( available>=nCellKey ){
- c = pCur->xCompare(pCur->pArg, nCellKey, pCellKey, nKey, pKey);
- }else{
- pCellKey = sqliteMallocRaw( nCellKey );
- if( pCellKey==0 ) return SQLITE_NOMEM;
- rc = sqlite3BtreeKey(pCur, 0, nCellKey, (void *)pCellKey);
- c = pCur->xCompare(pCur->pArg, nCellKey, pCellKey, nKey, pKey);
- sqliteFree(pCellKey);
- if( rc ) return rc;
- }
- }
- if( c==0 ){
- if( pPage->leafData && !pPage->leaf ){
- lwr = pCur->idx;
- upr = lwr - 1;
- break;
- }else{
- if( pRes ) *pRes = 0;
- return SQLITE_OK;
- }
- }
- if( c<0 ){
- lwr = pCur->idx+1;
- }else{
- upr = pCur->idx-1;
- }
- }
- assert( lwr==upr+1 );
- assert( pPage->isInit );
- if( pPage->leaf ){
- chldPg = 0;
- }else if( lwr>=pPage->nCell ){
- chldPg = get4byte(&pPage->aData[pPage->hdrOffset+8]);
- }else{
- chldPg = get4byte(findCell(pPage, lwr));
- }
- if( chldPg==0 ){
- assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
- if( pRes ) *pRes = c;
- return SQLITE_OK;
- }
- pCur->idx = lwr;
- pCur->info.nSize = 0;
- rc = moveToChild(pCur, chldPg);
- if( rc ){
- return rc;
- }
- }
- /* NOT REACHED */
-}
-
-/*
-** Return TRUE if the cursor is not pointing at an entry of the table.
-**
-** TRUE will be returned after a call to sqlite3BtreeNext() moves
-** past the last entry in the table or sqlite3BtreePrev() moves past
-** the first entry. TRUE is also returned if the table is empty.
-*/
-int sqlite3BtreeEof(BtCursor *pCur){
- return pCur->isValid==0;
-}
-
-/*
-** Advance the cursor to the next entry in the database. If
-** successful then set *pRes=0. If the cursor
-** was already pointing to the last entry in the database before
-** this routine was called, then set *pRes=1.
-*/
-int sqlite3BtreeNext(BtCursor *pCur, int *pRes){
- int rc;
- MemPage *pPage = pCur->pPage;
-
- assert( pRes!=0 );
- if( pCur->isValid==0 ){
- *pRes = 1;
- return SQLITE_OK;
- }
- assert( pPage->isInit );
- assert( pCur->idx<pPage->nCell );
- pCur->idx++;
- pCur->info.nSize = 0;
- if( pCur->idx>=pPage->nCell ){
- if( !pPage->leaf ){
- rc = moveToChild(pCur, get4byte(&pPage->aData[pPage->hdrOffset+8]));
- if( rc ) return rc;
- rc = moveToLeftmost(pCur);
- *pRes = 0;
- return rc;
- }
- do{
- if( isRootPage(pPage) ){
- *pRes = 1;
- pCur->isValid = 0;
- return SQLITE_OK;
- }
- moveToParent(pCur);
- pPage = pCur->pPage;
- }while( pCur->idx>=pPage->nCell );
- *pRes = 0;
- if( pPage->leafData ){
- rc = sqlite3BtreeNext(pCur, pRes);
- }else{
- rc = SQLITE_OK;
- }
- return rc;
- }
- *pRes = 0;
- if( pPage->leaf ){
- return SQLITE_OK;
- }
- rc = moveToLeftmost(pCur);
- return rc;
-}
-
-/*
-** Step the cursor to the back to the previous entry in the database. If
-** successful then set *pRes=0. If the cursor
-** was already pointing to the first entry in the database before
-** this routine was called, then set *pRes=1.
-*/
-int sqlite3BtreePrevious(BtCursor *pCur, int *pRes){
- int rc;
- Pgno pgno;
- MemPage *pPage;
- if( pCur->isValid==0 ){
- *pRes = 1;
- return SQLITE_OK;
- }
- pPage = pCur->pPage;
- assert( pPage->isInit );
- assert( pCur->idx>=0 );
- if( !pPage->leaf ){
- pgno = get4byte( findCell(pPage, pCur->idx) );
- rc = moveToChild(pCur, pgno);
- if( rc ) return rc;
- rc = moveToRightmost(pCur);
- }else{
- while( pCur->idx==0 ){
- if( isRootPage(pPage) ){
- pCur->isValid = 0;
- *pRes = 1;
- return SQLITE_OK;
- }
- moveToParent(pCur);
- pPage = pCur->pPage;
- }
- pCur->idx--;
- pCur->info.nSize = 0;
- if( pPage->leafData ){
- rc = sqlite3BtreePrevious(pCur, pRes);
- }else{
- rc = SQLITE_OK;
- }
- }
- *pRes = 0;
- return rc;
-}
-
-/*
-** The TRACE macro will print high-level status information about the
-** btree operation when the global variable sqlite3_btree_trace is
-** enabled.
-*/
-#if SQLITE_TEST
-# define TRACE(X) if( sqlite3_btree_trace )\
- { sqlite3DebugPrintf X; fflush(stdout); }
-#else
-# define TRACE(X)
-#endif
-int sqlite3_btree_trace=0; /* True to enable tracing */
-
-/*
-** Allocate a new page from the database file.
-**
-** The new page is marked as dirty. (In other words, sqlite3pager_write()
-** has already been called on the new page.) The new page has also
-** been referenced and the calling routine is responsible for calling
-** sqlite3pager_unref() on the new page when it is done.
-**
-** SQLITE_OK is returned on success. Any other return value indicates
-** an error. *ppPage and *pPgno are undefined in the event of an error.
-** Do not invoke sqlite3pager_unref() on *ppPage if an error is returned.
-**
-** If the "nearby" parameter is not 0, then a (feeble) effort is made to
-** locate a page close to the page number "nearby". This can be used in an
-** attempt to keep related pages close to each other in the database file,
-** which in turn can make database access faster.
-*/
-static int allocatePage(Btree *pBt, MemPage **ppPage, Pgno *pPgno, Pgno nearby){
- MemPage *pPage1;
- int rc;
- int n; /* Number of pages on the freelist */
- int k; /* Number of leaves on the trunk of the freelist */
-
- pPage1 = pBt->pPage1;
- n = get4byte(&pPage1->aData[36]);
- if( n>0 ){
- /* There are pages on the freelist. Reuse one of those pages. */
- MemPage *pTrunk;
- rc = sqlite3pager_write(pPage1->aData);
- if( rc ) return rc;
- put4byte(&pPage1->aData[36], n-1);
- rc = getPage(pBt, get4byte(&pPage1->aData[32]), &pTrunk);
- if( rc ) return rc;
- rc = sqlite3pager_write(pTrunk->aData);
- if( rc ){
- releasePage(pTrunk);
- return rc;
- }
- k = get4byte(&pTrunk->aData[4]);
- if( k==0 ){
- /* The trunk has no leaves. So extract the trunk page itself and
- ** use it as the newly allocated page */
- *pPgno = get4byte(&pPage1->aData[32]);
- memcpy(&pPage1->aData[32], &pTrunk->aData[0], 4);
- *ppPage = pTrunk;
- TRACE(("ALLOCATE: %d trunk - %d free pages left\n", *pPgno, n-1));
- }else if( k>pBt->usableSize/4 - 8 ){
- /* Value of k is out of range. Database corruption */
- return SQLITE_CORRUPT; /* bkpt-CORRUPT */
- }else{
- /* Extract a leaf from the trunk */
- int closest;
- unsigned char *aData = pTrunk->aData;
- if( nearby>0 ){
- int i, dist;
- closest = 0;
- dist = get4byte(&aData[8]) - nearby;
- if( dist<0 ) dist = -dist;
- for(i=1; i<k; i++){
- int d2 = get4byte(&aData[8+i*4]) - nearby;
- if( d2<0 ) d2 = -d2;
- if( d2<dist ) closest = i;
- }
- }else{
- closest = 0;
- }
- *pPgno = get4byte(&aData[8+closest*4]);
- if( *pPgno>sqlite3pager_pagecount(pBt->pPager) ){
- /* Free page off the end of the file */
- return SQLITE_CORRUPT; /* bkpt-CORRUPT */
- }
- TRACE(("ALLOCATE: %d was leaf %d of %d on trunk %d: %d more free pages\n",
- *pPgno, closest+1, k, pTrunk->pgno, n-1));
- if( closest<k-1 ){
- memcpy(&aData[8+closest*4], &aData[4+k*4], 4);
- }
- put4byte(&aData[4], k-1);
- rc = getPage(pBt, *pPgno, ppPage);
- releasePage(pTrunk);
- if( rc==SQLITE_OK ){
- sqlite3pager_dont_rollback((*ppPage)->aData);
- rc = sqlite3pager_write((*ppPage)->aData);
- }
- }
- }else{
- /* There are no pages on the freelist, so create a new page at the
- ** end of the file */
- *pPgno = sqlite3pager_pagecount(pBt->pPager) + 1;
- rc = getPage(pBt, *pPgno, ppPage);
- if( rc ) return rc;
- rc = sqlite3pager_write((*ppPage)->aData);
- TRACE(("ALLOCATE: %d from end of file\n", *pPgno));
- }
- return rc;
-}
-
-/*
-** Add a page of the database file to the freelist.
-**
-** sqlite3pager_unref() is NOT called for pPage.
-*/
-static int freePage(MemPage *pPage){
- Btree *pBt = pPage->pBt;
- MemPage *pPage1 = pBt->pPage1;
- int rc, n, k;
-
- /* Prepare the page for freeing */
- assert( pPage->pgno>1 );
- pPage->isInit = 0;
- releasePage(pPage->pParent);
- pPage->pParent = 0;
-
- /* Increment the free page count on pPage1 */
- rc = sqlite3pager_write(pPage1->aData);
- if( rc ) return rc;
- n = get4byte(&pPage1->aData[36]);
- put4byte(&pPage1->aData[36], n+1);
-
- if( n==0 ){
- /* This is the first free page */
- rc = sqlite3pager_write(pPage->aData);
- if( rc ) return rc;
- memset(pPage->aData, 0, 8);
- put4byte(&pPage1->aData[32], pPage->pgno);
- TRACE(("FREE-PAGE: %d first\n", pPage->pgno));
- }else{
- /* Other free pages already exist. Retrive the first trunk page
- ** of the freelist and find out how many leaves it has. */
- MemPage *pTrunk;
- rc = getPage(pBt, get4byte(&pPage1->aData[32]), &pTrunk);
- if( rc ) return rc;
- k = get4byte(&pTrunk->aData[4]);
- if( k>=pBt->usableSize/4 - 8 ){
- /* The trunk is full. Turn the page being freed into a new
- ** trunk page with no leaves. */
- rc = sqlite3pager_write(pPage->aData);
- if( rc ) return rc;
- put4byte(pPage->aData, pTrunk->pgno);
- put4byte(&pPage->aData[4], 0);
- put4byte(&pPage1->aData[32], pPage->pgno);
- TRACE(("FREE-PAGE: %d new trunk page replacing %d\n",
- pPage->pgno, pTrunk->pgno));
- }else{
- /* Add the newly freed page as a leaf on the current trunk */
- rc = sqlite3pager_write(pTrunk->aData);
- if( rc ) return rc;
- put4byte(&pTrunk->aData[4], k+1);
- put4byte(&pTrunk->aData[8+k*4], pPage->pgno);
- sqlite3pager_dont_write(pBt->pPager, pPage->pgno);
- TRACE(("FREE-PAGE: %d leaf on trunk page %d\n",pPage->pgno,pTrunk->pgno));
- }
- releasePage(pTrunk);
- }
- return rc;
-}
-
-/*
-** Free any overflow pages associated with the given Cell.
-*/
-static int clearCell(MemPage *pPage, unsigned char *pCell){
- Btree *pBt = pPage->pBt;
- CellInfo info;
- Pgno ovflPgno;
- int rc;
-
- parseCellPtr(pPage, pCell, &info);
- if( info.iOverflow==0 ){
- return SQLITE_OK; /* No overflow pages. Return without doing anything */
- }
- ovflPgno = get4byte(&pCell[info.iOverflow]);
- while( ovflPgno!=0 ){
- MemPage *pOvfl;
- rc = getPage(pBt, ovflPgno, &pOvfl);
- if( rc ) return rc;
- ovflPgno = get4byte(pOvfl->aData);
- rc = freePage(pOvfl);
- if( rc ) return rc;
- sqlite3pager_unref(pOvfl->aData);
- }
- return SQLITE_OK;
-}
-
-/*
-** Create the byte sequence used to represent a cell on page pPage
-** and write that byte sequence into pCell[]. Overflow pages are
-** allocated and filled in as necessary. The calling procedure
-** is responsible for making sure sufficient space has been allocated
-** for pCell[].
-**
-** Note that pCell does not necessary need to point to the pPage->aData
-** area. pCell might point to some temporary storage. The cell will
-** be constructed in this temporary area then copied into pPage->aData
-** later.
-*/
-static int fillInCell(
- MemPage *pPage, /* The page that contains the cell */
- unsigned char *pCell, /* Complete text of the cell */
- const void *pKey, i64 nKey, /* The key */
- const void *pData,int nData, /* The data */
- int *pnSize /* Write cell size here */
-){
- int nPayload;
- const u8 *pSrc;
- int nSrc, n, rc;
- int spaceLeft;
- MemPage *pOvfl = 0;
- MemPage *pToRelease = 0;
- unsigned char *pPrior;
- unsigned char *pPayload;
- Btree *pBt = pPage->pBt;
- Pgno pgnoOvfl = 0;
- int nHeader;
- CellInfo info;
-
- /* Fill in the header. */
- nHeader = 0;
- if( !pPage->leaf ){
- nHeader += 4;
- }
- if( pPage->hasData ){
- nHeader += putVarint(&pCell[nHeader], nData);
- }else{
- nData = 0;
- }
- nHeader += putVarint(&pCell[nHeader], *(u64*)&nKey);
- parseCellPtr(pPage, pCell, &info);
- assert( info.nHeader==nHeader );
- assert( info.nKey==nKey );
- assert( info.nData==nData );
-
- /* Fill in the payload */
- nPayload = nData;
- if( pPage->intKey ){
- pSrc = pData;
- nSrc = nData;
- nData = 0;
- }else{
- nPayload += nKey;
- pSrc = pKey;
- nSrc = nKey;
- }
- *pnSize = info.nSize;
- spaceLeft = info.nLocal;
- pPayload = &pCell[nHeader];
- pPrior = &pCell[info.iOverflow];
-
- while( nPayload>0 ){
- if( spaceLeft==0 ){
- rc = allocatePage(pBt, &pOvfl, &pgnoOvfl, pgnoOvfl);
- if( rc ){
- releasePage(pToRelease);
- clearCell(pPage, pCell);
- return rc;
- }
- put4byte(pPrior, pgnoOvfl);
- releasePage(pToRelease);
- pToRelease = pOvfl;
- pPrior = pOvfl->aData;
- put4byte(pPrior, 0);
- pPayload = &pOvfl->aData[4];
- spaceLeft = pBt->usableSize - 4;
- }
- n = nPayload;
- if( n>spaceLeft ) n = spaceLeft;
- if( n>nSrc ) n = nSrc;
- memcpy(pPayload, pSrc, n);
- nPayload -= n;
- pPayload += n;
- pSrc += n;
- nSrc -= n;
- spaceLeft -= n;
- if( nSrc==0 ){
- nSrc = nData;
- pSrc = pData;
- }
- }
- releasePage(pToRelease);
- return SQLITE_OK;
-}
-
-/*
-** Change the MemPage.pParent pointer on the page whose number is
-** given in the second argument so that MemPage.pParent holds the
-** pointer in the third argument.
-*/
-static void reparentPage(Btree *pBt, Pgno pgno, MemPage *pNewParent, int idx){
- MemPage *pThis;
- unsigned char *aData;
-
- if( pgno==0 ) return;
- assert( pBt->pPager!=0 );
- aData = sqlite3pager_lookup(pBt->pPager, pgno);
- if( aData ){
- pThis = (MemPage*)&aData[pBt->pageSize];
- assert( pThis->aData==aData );
- if( pThis->isInit ){
- if( pThis->pParent!=pNewParent ){
- if( pThis->pParent ) sqlite3pager_unref(pThis->pParent->aData);
- pThis->pParent = pNewParent;
- if( pNewParent ) sqlite3pager_ref(pNewParent->aData);
- }
- pThis->idxParent = idx;
- }
- sqlite3pager_unref(aData);
- }
-}
-
-/*
-** Change the pParent pointer of all children of pPage to point back
-** to pPage.
-**
-** In other words, for every child of pPage, invoke reparentPage()
-** to make sure that each child knows that pPage is its parent.
-**
-** This routine gets called after you memcpy() one page into
-** another.
-*/
-static void reparentChildPages(MemPage *pPage){
- int i;
- Btree *pBt;
-
- if( pPage->leaf ) return;
- pBt = pPage->pBt;
- for(i=0; i<pPage->nCell; i++){
- reparentPage(pBt, get4byte(findCell(pPage,i)), pPage, i);
- }
- reparentPage(pBt, get4byte(&pPage->aData[pPage->hdrOffset+8]), pPage, i);
- pPage->idxShift = 0;
-}
-
-/*
-** Remove the i-th cell from pPage. This routine effects pPage only.
-** The cell content is not freed or deallocated. It is assumed that
-** the cell content has been copied someplace else. This routine just
-** removes the reference to the cell from pPage.
-**
-** "sz" must be the number of bytes in the cell.
-*/
-static void dropCell(MemPage *pPage, int idx, int sz){
- int i; /* Loop counter */
- int pc; /* Offset to cell content of cell being deleted */
- u8 *data; /* pPage->aData */
- u8 *ptr; /* Used to move bytes around within data[] */
-
- assert( idx>=0 && idx<pPage->nCell );
- assert( sz==cellSize(pPage, idx) );
- assert( sqlite3pager_iswriteable(pPage->aData) );
- data = pPage->aData;
- ptr = &data[pPage->cellOffset + 2*idx];
- pc = get2byte(ptr);
- assert( pc>10 && pc+sz<=pPage->pBt->usableSize );
- freeSpace(pPage, pc, sz);
- for(i=idx+1; i<pPage->nCell; i++, ptr+=2){
- ptr[0] = ptr[2];
- ptr[1] = ptr[3];
- }
- pPage->nCell--;
- put2byte(&data[pPage->hdrOffset+3], pPage->nCell);
- pPage->nFree += 2;
- pPage->idxShift = 1;
-}
-
-/*
-** Insert a new cell on pPage at cell index "i". pCell points to the
-** content of the cell.
-**
-** If the cell content will fit on the page, then put it there. If it
-** will not fit, then make a copy of the cell content into pTemp if
-** pTemp is not null. Regardless of pTemp, allocate a new entry
-** in pPage->aOvfl[] and make it point to the cell content (either
-** in pTemp or the original pCell) and also record its index.
-** Allocating a new entry in pPage->aCell[] implies that
-** pPage->nOverflow is incremented.
-*/
-static void insertCell(
- MemPage *pPage, /* Page into which we are copying */
- int i, /* New cell becomes the i-th cell of the page */
- u8 *pCell, /* Content of the new cell */
- int sz, /* Bytes of content in pCell */
- u8 *pTemp /* Temp storage space for pCell, if needed */
-){
- int idx; /* Where to write new cell content in data[] */
- int j; /* Loop counter */
- int top; /* First byte of content for any cell in data[] */
- int end; /* First byte past the last cell pointer in data[] */
- int ins; /* Index in data[] where new cell pointer is inserted */
- int hdr; /* Offset into data[] of the page header */
- int cellOffset; /* Address of first cell pointer in data[] */
- u8 *data; /* The content of the whole page */
- u8 *ptr; /* Used for moving information around in data[] */
-
- assert( i>=0 && i<=pPage->nCell+pPage->nOverflow );
- assert( sz==cellSizePtr(pPage, pCell) );
- assert( sqlite3pager_iswriteable(pPage->aData) );
- if( pPage->nOverflow || sz+2>pPage->nFree ){
- if( pTemp ){
- memcpy(pTemp, pCell, sz);
- pCell = pTemp;
- }
- j = pPage->nOverflow++;
- assert( j<sizeof(pPage->aOvfl)/sizeof(pPage->aOvfl[0]) );
- pPage->aOvfl[j].pCell = pCell;
- pPage->aOvfl[j].idx = i;
- pPage->nFree = 0;
- }else{
- data = pPage->aData;
- hdr = pPage->hdrOffset;
- top = get2byte(&data[hdr+5]);
- cellOffset = pPage->cellOffset;
- end = cellOffset + 2*pPage->nCell + 2;
- ins = cellOffset + 2*i;
- if( end > top - sz ){
- defragmentPage(pPage);
- top = get2byte(&data[hdr+5]);
- assert( end + sz <= top );
- }
- idx = allocateSpace(pPage, sz);
- assert( idx>0 );
- assert( end <= get2byte(&data[hdr+5]) );
- pPage->nCell++;
- pPage->nFree -= 2;
- memcpy(&data[idx], pCell, sz);
- for(j=end-2, ptr=&data[j]; j>ins; j-=2, ptr-=2){
- ptr[0] = ptr[-2];
- ptr[1] = ptr[-1];
- }
- put2byte(&data[ins], idx);
- put2byte(&data[hdr+3], pPage->nCell);
- pPage->idxShift = 1;
- pageIntegrity(pPage);
- }
-}
-
-/*
-** Add a list of cells to a page. The page should be initially empty.
-** The cells are guaranteed to fit on the page.
-*/
-static void assemblePage(
- MemPage *pPage, /* The page to be assemblied */
- int nCell, /* The number of cells to add to this page */
- u8 **apCell, /* Pointers to cell bodies */
- int *aSize /* Sizes of the cells */
-){
- int i; /* Loop counter */
- int totalSize; /* Total size of all cells */
- int hdr; /* Index of page header */
- int cellptr; /* Address of next cell pointer */
- int cellbody; /* Address of next cell body */
- u8 *data; /* Data for the page */
-
- assert( pPage->nOverflow==0 );
- totalSize = 0;
- for(i=0; i<nCell; i++){
- totalSize += aSize[i];
- }
- assert( totalSize+2*nCell<=pPage->nFree );
- assert( pPage->nCell==0 );
- cellptr = pPage->cellOffset;
- data = pPage->aData;
- hdr = pPage->hdrOffset;
- put2byte(&data[hdr+3], nCell);
- cellbody = allocateSpace(pPage, totalSize);
- assert( cellbody>0 );
- assert( pPage->nFree >= 2*nCell );
- pPage->nFree -= 2*nCell;
- for(i=0; i<nCell; i++){
- put2byte(&data[cellptr], cellbody);
- memcpy(&data[cellbody], apCell[i], aSize[i]);
- cellptr += 2;
- cellbody += aSize[i];
- }
- assert( cellbody==pPage->pBt->usableSize );
- pPage->nCell = nCell;
-}
-
-/*
-** GCC does not define the offsetof() macro so we'll have to do it
-** ourselves.
-*/
-#ifndef offsetof
-#define offsetof(STRUCTURE,FIELD) ((int)((char*)&((STRUCTURE*)0)->FIELD))
-#endif
-
-/*
-** The following parameters determine how many adjacent pages get involved
-** in a balancing operation. NN is the number of neighbors on either side
-** of the page that participate in the balancing operation. NB is the
-** total number of pages that participate, including the target page and
-** NN neighbors on either side.
-**
-** The minimum value of NN is 1 (of course). Increasing NN above 1
-** (to 2 or 3) gives a modest improvement in SELECT and DELETE performance
-** in exchange for a larger degradation in INSERT and UPDATE performance.
-** The value of NN appears to give the best results overall.
-*/
-#define NN 1 /* Number of neighbors on either side of pPage */
-#define NB (NN*2+1) /* Total pages involved in the balance */
-
-/* Forward reference */
-static int balance(MemPage*);
-
-/*
-** This routine redistributes Cells on pPage and up to NN*2 siblings
-** of pPage so that all pages have about the same amount of free space.
-** Usually NN siblings on either side of pPage is used in the balancing,
-** though more siblings might come from one side if pPage is the first
-** or last child of its parent. If pPage has fewer than 2*NN siblings
-** (something which can only happen if pPage is the root page or a
-** child of root) then all available siblings participate in the balancing.
-**
-** The number of siblings of pPage might be increased or decreased by one or
-** two in an effort to keep pages nearly full but not over full. The root page
-** is special and is allowed to be nearly empty. If pPage is
-** the root page, then the depth of the tree might be increased
-** or decreased by one, as necessary, to keep the root page from being
-** overfull or completely empty.
-**
-** Note that when this routine is called, some of the Cells on pPage
-** might not actually be stored in pPage->aData[]. This can happen
-** if the page is overfull. Part of the job of this routine is to
-** make sure all Cells for pPage once again fit in pPage->aData[].
-**
-** In the course of balancing the siblings of pPage, the parent of pPage
-** might become overfull or underfull. If that happens, then this routine
-** is called recursively on the parent.
-**
-** If this routine fails for any reason, it might leave the database
-** in a corrupted state. So if this routine fails, the database should
-** be rolled back.
-*/
-static int balance_nonroot(MemPage *pPage){
- MemPage *pParent; /* The parent of pPage */
- Btree *pBt; /* The whole database */
- int nCell = 0; /* Number of cells in aCell[] */
- int nOld; /* Number of pages in apOld[] */
- int nNew; /* Number of pages in apNew[] */
- int nDiv; /* Number of cells in apDiv[] */
- int i, j, k; /* Loop counters */
- int idx; /* Index of pPage in pParent->aCell[] */
- int nxDiv; /* Next divider slot in pParent->aCell[] */
- int rc; /* The return code */
- int leafCorrection; /* 4 if pPage is a leaf. 0 if not */
- int leafData; /* True if pPage is a leaf of a LEAFDATA tree */
- int usableSpace; /* Bytes in pPage beyond the header */
- int pageFlags; /* Value of pPage->aData[0] */
- int subtotal; /* Subtotal of bytes in cells on one page */
- int iSpace = 0; /* First unused byte of aSpace[] */
- int mxCellPerPage; /* Maximum number of cells in one page */
- MemPage *apOld[NB]; /* pPage and up to two siblings */
- Pgno pgnoOld[NB]; /* Page numbers for each page in apOld[] */
- MemPage *apCopy[NB]; /* Private copies of apOld[] pages */
- MemPage *apNew[NB+2]; /* pPage and up to NB siblings after balancing */
- Pgno pgnoNew[NB+2]; /* Page numbers for each page in apNew[] */
- int idxDiv[NB]; /* Indices of divider cells in pParent */
- u8 *apDiv[NB]; /* Divider cells in pParent */
- int cntNew[NB+2]; /* Index in aCell[] of cell after i-th page */
- int szNew[NB+2]; /* Combined size of cells place on i-th page */
- u8 **apCell; /* All cells begin balanced */
- int *szCell; /* Local size of all cells in apCell[] */
- u8 *aCopy[NB]; /* Space for holding data of apCopy[] */
- u8 *aSpace; /* Space to hold copies of dividers cells */
-
- /*
- ** Find the parent page.
- */
- assert( pPage->isInit );
- assert( sqlite3pager_iswriteable(pPage->aData) );
- pBt = pPage->pBt;
- pParent = pPage->pParent;
- sqlite3pager_write(pParent->aData);
- assert( pParent );
- TRACE(("BALANCE: begin page %d child of %d\n", pPage->pgno, pParent->pgno));
-
- /*
- ** Allocate space for memory structures
- */
- mxCellPerPage = MX_CELL(pBt);
- apCell = sqliteMallocRaw(
- (mxCellPerPage+2)*NB*(sizeof(u8*)+sizeof(int))
- + sizeof(MemPage)*NB
- + pBt->pageSize*(5+NB)
- );
- if( apCell==0 ){
- return SQLITE_NOMEM;
- }
- szCell = (int*)&apCell[(mxCellPerPage+2)*NB];
- aCopy[0] = (u8*)&szCell[(mxCellPerPage+2)*NB];
- for(i=1; i<NB; i++){
- aCopy[i] = &aCopy[i-1][pBt->pageSize+sizeof(MemPage)];
- }
- aSpace = &aCopy[NB-1][pBt->pageSize+sizeof(MemPage)];
-
- /*
- ** Find the cell in the parent page whose left child points back
- ** to pPage. The "idx" variable is the index of that cell. If pPage
- ** is the rightmost child of pParent then set idx to pParent->nCell
- */
- if( pParent->idxShift ){
- Pgno pgno;
- pgno = pPage->pgno;
- assert( pgno==sqlite3pager_pagenumber(pPage->aData) );
- for(idx=0; idx<pParent->nCell; idx++){
- if( get4byte(findCell(pParent, idx))==pgno ){
- break;
- }
- }
- assert( idx<pParent->nCell
- || get4byte(&pParent->aData[pParent->hdrOffset+8])==pgno );
- }else{
- idx = pPage->idxParent;
- }
-
- /*
- ** Initialize variables so that it will be safe to jump
- ** directly to balance_cleanup at any moment.
- */
- nOld = nNew = 0;
- sqlite3pager_ref(pParent->aData);
-
- /*
- ** Find sibling pages to pPage and the cells in pParent that divide
- ** the siblings. An attempt is made to find NN siblings on either
- ** side of pPage. More siblings are taken from one side, however, if
- ** pPage there are fewer than NN siblings on the other side. If pParent
- ** has NB or fewer children then all children of pParent are taken.
- */
- nxDiv = idx - NN;
- if( nxDiv + NB > pParent->nCell ){
- nxDiv = pParent->nCell - NB + 1;
- }
- if( nxDiv<0 ){
- nxDiv = 0;
- }
- nDiv = 0;
- for(i=0, k=nxDiv; i<NB; i++, k++){
- if( k<pParent->nCell ){
- idxDiv[i] = k;
- apDiv[i] = findCell(pParent, k);
- nDiv++;
- assert( !pParent->leaf );
- pgnoOld[i] = get4byte(apDiv[i]);
- }else if( k==pParent->nCell ){
- pgnoOld[i] = get4byte(&pParent->aData[pParent->hdrOffset+8]);
- }else{
- break;
- }
- rc = getAndInitPage(pBt, pgnoOld[i], &apOld[i], pParent);
- if( rc ) goto balance_cleanup;
- apOld[i]->idxParent = k;
- apCopy[i] = 0;
- assert( i==nOld );
- nOld++;
- }
-
- /*
- ** Make copies of the content of pPage and its siblings into aOld[].
- ** The rest of this function will use data from the copies rather
- ** that the original pages since the original pages will be in the
- ** process of being overwritten.
- */
- for(i=0; i<nOld; i++){
- MemPage *p = apCopy[i] = (MemPage*)&aCopy[i][pBt->pageSize];
- p->aData = &((u8*)p)[-pBt->pageSize];
- memcpy(p->aData, apOld[i]->aData, pBt->pageSize + sizeof(MemPage));
- p->aData = &((u8*)p)[-pBt->pageSize];
- }
-
- /*
- ** Load pointers to all cells on sibling pages and the divider cells
- ** into the local apCell[] array. Make copies of the divider cells
- ** into space obtained form aSpace[] and remove the the divider Cells
- ** from pParent.
- **
- ** If the siblings are on leaf pages, then the child pointers of the
- ** divider cells are stripped from the cells before they are copied
- ** into aSpace[]. In this way, all cells in apCell[] are without
- ** child pointers. If siblings are not leaves, then all cell in
- ** apCell[] include child pointers. Either way, all cells in apCell[]
- ** are alike.
- **
- ** leafCorrection: 4 if pPage is a leaf. 0 if pPage is not a leaf.
- ** leafData: 1 if pPage holds key+data and pParent holds only keys.
- */
- nCell = 0;
- leafCorrection = pPage->leaf*4;
- leafData = pPage->leafData && pPage->leaf;
- for(i=0; i<nOld; i++){
- MemPage *pOld = apCopy[i];
- int limit = pOld->nCell+pOld->nOverflow;
- for(j=0; j<limit; j++){
- apCell[nCell] = findOverflowCell(pOld, j);
- szCell[nCell] = cellSizePtr(pOld, apCell[nCell]);
- nCell++;
- }
- if( i<nOld-1 ){
- int sz = cellSizePtr(pParent, apDiv[i]);
- if( leafData ){
- /* With the LEAFDATA flag, pParent cells hold only INTKEYs that
- ** are duplicates of keys on the child pages. We need to remove
- ** the divider cells from pParent, but the dividers cells are not
- ** added to apCell[] because they are duplicates of child cells.
- */
- dropCell(pParent, nxDiv, sz);
- }else{
- u8 *pTemp;
- szCell[nCell] = sz;
- pTemp = &aSpace[iSpace];
- iSpace += sz;
- assert( iSpace<=pBt->pageSize*5 );
- memcpy(pTemp, apDiv[i], sz);
- apCell[nCell] = pTemp+leafCorrection;
- dropCell(pParent, nxDiv, sz);
- szCell[nCell] -= leafCorrection;
- assert( get4byte(pTemp)==pgnoOld[i] );
- if( !pOld->leaf ){
- assert( leafCorrection==0 );
- /* The right pointer of the child page pOld becomes the left
- ** pointer of the divider cell */
- memcpy(apCell[nCell], &pOld->aData[pOld->hdrOffset+8], 4);
- }else{
- assert( leafCorrection==4 );
- }
- nCell++;
- }
- }
- }
-
- /*
- ** Figure out the number of pages needed to hold all nCell cells.
- ** Store this number in "k". Also compute szNew[] which is the total
- ** size of all cells on the i-th page and cntNew[] which is the index
- ** in apCell[] of the cell that divides page i from page i+1.
- ** cntNew[k] should equal nCell.
- **
- ** Values computed by this block:
- **
- ** k: The total number of sibling pages
- ** szNew[i]: Spaced used on the i-th sibling page.
- ** cntNew[i]: Index in apCell[] and szCell[] for the first cell to
- ** the right of the i-th sibling page.
- ** usableSpace: Number of bytes of space available on each sibling.
- **
- */
- usableSpace = pBt->usableSize - 12 + leafCorrection;
- for(subtotal=k=i=0; i<nCell; i++){
- subtotal += szCell[i] + 2;
- if( subtotal > usableSpace ){
- szNew[k] = subtotal - szCell[i];
- cntNew[k] = i;
- if( leafData ){ i--; }
- subtotal = 0;
- k++;
- }
- }
- szNew[k] = subtotal;
- cntNew[k] = nCell;
- k++;
-
- /*
- ** The packing computed by the previous block is biased toward the siblings
- ** on the left side. The left siblings are always nearly full, while the
- ** right-most sibling might be nearly empty. This block of code attempts
- ** to adjust the packing of siblings to get a better balance.
- **
- ** This adjustment is more than an optimization. The packing above might
- ** be so out of balance as to be illegal. For example, the right-most
- ** sibling might be completely empty. This adjustment is not optional.
- */
- for(i=k-1; i>0; i--){
- int szRight = szNew[i]; /* Size of sibling on the right */
- int szLeft = szNew[i-1]; /* Size of sibling on the left */
- int r; /* Index of right-most cell in left sibling */
- int d; /* Index of first cell to the left of right sibling */
-
- r = cntNew[i-1] - 1;
- d = r + 1 - leafData;
- while( szRight==0 || szRight+szCell[d]+2<=szLeft-(szCell[r]+2) ){
- szRight += szCell[d] + 2;
- szLeft -= szCell[r] + 2;
- cntNew[i-1]--;
- r = cntNew[i-1] - 1;
- d = r + 1 - leafData;
- }
- szNew[i] = szRight;
- szNew[i-1] = szLeft;
- }
- assert( cntNew[0]>0 );
-
- /*
- ** Allocate k new pages. Reuse old pages where possible.
- */
- assert( pPage->pgno>1 );
- pageFlags = pPage->aData[0];
- for(i=0; i<k; i++){
- MemPage *pNew;
- if( i<nOld ){
- pNew = apNew[i] = apOld[i];
- pgnoNew[i] = pgnoOld[i];
- apOld[i] = 0;
- sqlite3pager_write(pNew->aData);
- }else{
- rc = allocatePage(pBt, &pNew, &pgnoNew[i], pgnoNew[i-1]);
- if( rc ) goto balance_cleanup;
- apNew[i] = pNew;
- }
- nNew++;
- zeroPage(pNew, pageFlags);
- }
-
- /* Free any old pages that were not reused as new pages.
- */
- while( i<nOld ){
- rc = freePage(apOld[i]);
- if( rc ) goto balance_cleanup;
- releasePage(apOld[i]);
- apOld[i] = 0;
- i++;
- }
-
- /*
- ** Put the new pages in accending order. This helps to
- ** keep entries in the disk file in order so that a scan
- ** of the table is a linear scan through the file. That
- ** in turn helps the operating system to deliver pages
- ** from the disk more rapidly.
- **
- ** An O(n^2) insertion sort algorithm is used, but since
- ** n is never more than NB (a small constant), that should
- ** not be a problem.
- **
- ** When NB==3, this one optimization makes the database
- ** about 25% faster for large insertions and deletions.
- */
- for(i=0; i<k-1; i++){
- int minV = pgnoNew[i];
- int minI = i;
- for(j=i+1; j<k; j++){
- if( pgnoNew[j]<(unsigned)minV ){
- minI = j;
- minV = pgnoNew[j];
- }
- }
- if( minI>i ){
- int t;
- MemPage *pT;
- t = pgnoNew[i];
- pT = apNew[i];
- pgnoNew[i] = pgnoNew[minI];
- apNew[i] = apNew[minI];
- pgnoNew[minI] = t;
- apNew[minI] = pT;
- }
- }
- TRACE(("BALANCE: old: %d %d %d new: %d(%d) %d(%d) %d(%d) %d(%d) %d(%d)\n",
- pgnoOld[0],
- nOld>=2 ? pgnoOld[1] : 0,
- nOld>=3 ? pgnoOld[2] : 0,
- pgnoNew[0], szNew[0],
- nNew>=2 ? pgnoNew[1] : 0, nNew>=2 ? szNew[1] : 0,
- nNew>=3 ? pgnoNew[2] : 0, nNew>=3 ? szNew[2] : 0,
- nNew>=4 ? pgnoNew[3] : 0, nNew>=4 ? szNew[3] : 0,
- nNew>=5 ? pgnoNew[4] : 0, nNew>=5 ? szNew[4] : 0));
-
-
- /*
- ** Evenly distribute the data in apCell[] across the new pages.
- ** Insert divider cells into pParent as necessary.
- */
- j = 0;
- for(i=0; i<nNew; i++){
- MemPage *pNew = apNew[i];
- assert( pNew->pgno==pgnoNew[i] );
- assemblePage(pNew, cntNew[i]-j, &apCell[j], &szCell[j]);
- j = cntNew[i];
- assert( pNew->nCell>0 );
- assert( pNew->nOverflow==0 );
- if( i<nNew-1 && j<nCell ){
- u8 *pCell;
- u8 *pTemp;
- int sz;
- pCell = apCell[j];
- sz = szCell[j] + leafCorrection;
- if( !pNew->leaf ){
- memcpy(&pNew->aData[8], pCell, 4);
- pTemp = 0;
- }else if( leafData ){
- CellInfo info;
- j--;
- parseCellPtr(pNew, apCell[j], &info);
- pCell = &aSpace[iSpace];
- fillInCell(pParent, pCell, 0, info.nKey, 0, 0, &sz);
- iSpace += sz;
- assert( iSpace<=pBt->pageSize*5 );
- pTemp = 0;
- }else{
- pCell -= 4;
- pTemp = &aSpace[iSpace];
- iSpace += sz;
- assert( iSpace<=pBt->pageSize*5 );
- }
- insertCell(pParent, nxDiv, pCell, sz, pTemp);
- put4byte(findOverflowCell(pParent,nxDiv), pNew->pgno);
- j++;
- nxDiv++;
- }
- }
- assert( j==nCell );
- if( (pageFlags & PTF_LEAF)==0 ){
- memcpy(&apNew[nNew-1]->aData[8], &apCopy[nOld-1]->aData[8], 4);
- }
- if( nxDiv==pParent->nCell+pParent->nOverflow ){
- /* Right-most sibling is the right-most child of pParent */
- put4byte(&pParent->aData[pParent->hdrOffset+8], pgnoNew[nNew-1]);
- }else{
- /* Right-most sibling is the left child of the first entry in pParent
- ** past the right-most divider entry */
- put4byte(findOverflowCell(pParent, nxDiv), pgnoNew[nNew-1]);
- }
-
- /*
- ** Reparent children of all cells.
- */
- for(i=0; i<nNew; i++){
- reparentChildPages(apNew[i]);
- }
- reparentChildPages(pParent);
-
- /*
- ** Balance the parent page. Note that the current page (pPage) might
- ** have been added to the freelist is it might no longer be initialized.
- ** But the parent page will always be initialized.
- */
- assert( pParent->isInit );
- /* assert( pPage->isInit ); // No! pPage might have been added to freelist */
- /* pageIntegrity(pPage); // No! pPage might have been added to freelist */
- rc = balance(pParent);
-
- /*
- ** Cleanup before returning.
- */
-balance_cleanup:
- sqliteFree(apCell);
- for(i=0; i<nOld; i++){
- releasePage(apOld[i]);
- }
- for(i=0; i<nNew; i++){
- releasePage(apNew[i]);
- }
- releasePage(pParent);
- TRACE(("BALANCE: finished with %d: old=%d new=%d cells=%d\n",
- pPage->pgno, nOld, nNew, nCell));
- return rc;
-}
-
-/*
-** This routine is called for the root page of a btree when the root
-** page contains no cells. This is an opportunity to make the tree
-** shallower by one level.
-*/
-static int balance_shallower(MemPage *pPage){
- MemPage *pChild; /* The only child page of pPage */
- Pgno pgnoChild; /* Page number for pChild */
- int rc = SQLITE_OK; /* Return code from subprocedures */
- Btree *pBt; /* The main BTree structure */
- int mxCellPerPage; /* Maximum number of cells per page */
- u8 **apCell; /* All cells from pages being balanced */
- int *szCell; /* Local size of all cells */
-
- assert( pPage->pParent==0 );
- assert( pPage->nCell==0 );
- pBt = pPage->pBt;
- mxCellPerPage = MX_CELL(pBt);
- apCell = sqliteMallocRaw( mxCellPerPage*(sizeof(u8*)+sizeof(int)) );
- if( apCell==0 ) return SQLITE_NOMEM;
- szCell = (int*)&apCell[mxCellPerPage];
- if( pPage->leaf ){
- /* The table is completely empty */
- TRACE(("BALANCE: empty table %d\n", pPage->pgno));
- }else{
- /* The root page is empty but has one child. Transfer the
- ** information from that one child into the root page if it
- ** will fit. This reduces the depth of the tree by one.
- **
- ** If the root page is page 1, it has less space available than
- ** its child (due to the 100 byte header that occurs at the beginning
- ** of the database fle), so it might not be able to hold all of the
- ** information currently contained in the child. If this is the
- ** case, then do not do the transfer. Leave page 1 empty except
- ** for the right-pointer to the child page. The child page becomes
- ** the virtual root of the tree.
- */
- pgnoChild = get4byte(&pPage->aData[pPage->hdrOffset+8]);
- assert( pgnoChild>0 );
- assert( pgnoChild<=sqlite3pager_pagecount(pPage->pBt->pPager) );
- rc = getPage(pPage->pBt, pgnoChild, &pChild);
- if( rc ) goto end_shallow_balance;
- if( pPage->pgno==1 ){
- rc = initPage(pChild, pPage);
- if( rc ) goto end_shallow_balance;
- assert( pChild->nOverflow==0 );
- if( pChild->nFree>=100 ){
- /* The child information will fit on the root page, so do the
- ** copy */
- int i;
- zeroPage(pPage, pChild->aData[0]);
- for(i=0; i<pChild->nCell; i++){
- apCell[i] = findCell(pChild,i);
- szCell[i] = cellSizePtr(pChild, apCell[i]);
- }
- assemblePage(pPage, pChild->nCell, apCell, szCell);
- freePage(pChild);
- TRACE(("BALANCE: child %d transfer to page 1\n", pChild->pgno));
- }else{
- /* The child has more information that will fit on the root.
- ** The tree is already balanced. Do nothing. */
- TRACE(("BALANCE: child %d will not fit on page 1\n", pChild->pgno));
- }
- }else{
- memcpy(pPage->aData, pChild->aData, pPage->pBt->usableSize);
- pPage->isInit = 0;
- pPage->pParent = 0;
- rc = initPage(pPage, 0);
- assert( rc==SQLITE_OK );
- freePage(pChild);
- TRACE(("BALANCE: transfer child %d into root %d\n",
- pChild->pgno, pPage->pgno));
- }
- reparentChildPages(pPage);
- releasePage(pChild);
- }
-end_shallow_balance:
- sqliteFree(apCell);
- return rc;
-}
-
-
-/*
-** The root page is overfull
-**
-** When this happens, Create a new child page and copy the
-** contents of the root into the child. Then make the root
-** page an empty page with rightChild pointing to the new
-** child. Finally, call balance_internal() on the new child
-** to cause it to split.
-*/
-static int balance_deeper(MemPage *pPage){
- int rc; /* Return value from subprocedures */
- MemPage *pChild; /* Pointer to a new child page */
- Pgno pgnoChild; /* Page number of the new child page */
- Btree *pBt; /* The BTree */
- int usableSize; /* Total usable size of a page */
- u8 *data; /* Content of the parent page */
- u8 *cdata; /* Content of the child page */
- int hdr; /* Offset to page header in parent */
- int brk; /* Offset to content of first cell in parent */
-
- assert( pPage->pParent==0 );
- assert( pPage->nOverflow>0 );
- pBt = pPage->pBt;
- rc = allocatePage(pBt, &pChild, &pgnoChild, pPage->pgno);
- if( rc ) return rc;
- assert( sqlite3pager_iswriteable(pChild->aData) );
- usableSize = pBt->usableSize;
- data = pPage->aData;
- hdr = pPage->hdrOffset;
- brk = get2byte(&data[hdr+5]);
- cdata = pChild->aData;
- memcpy(cdata, &data[hdr], pPage->cellOffset+2*pPage->nCell-hdr);
- memcpy(&cdata[brk], &data[brk], usableSize-brk);
- rc = initPage(pChild, pPage);
- if( rc ) return rc;
- memcpy(pChild->aOvfl, pPage->aOvfl, pPage->nOverflow*sizeof(pPage->aOvfl[0]));
- pChild->nOverflow = pPage->nOverflow;
- if( pChild->nOverflow ){
- pChild->nFree = 0;
- }
- assert( pChild->nCell==pPage->nCell );
- zeroPage(pPage, pChild->aData[0] & ~PTF_LEAF);
- put4byte(&pPage->aData[pPage->hdrOffset+8], pgnoChild);
- TRACE(("BALANCE: copy root %d into %d\n", pPage->pgno, pChild->pgno));
- rc = balance_nonroot(pChild);
- releasePage(pChild);
- return rc;
-}
-
-/*
-** Decide if the page pPage needs to be balanced. If balancing is
-** required, call the appropriate balancing routine.
-*/
-static int balance(MemPage *pPage){
- int rc = SQLITE_OK;
- if( pPage->pParent==0 ){
- if( pPage->nOverflow>0 ){
- rc = balance_deeper(pPage);
- }
- if( pPage->nCell==0 ){
- rc = balance_shallower(pPage);
- }
- }else{
- if( pPage->nOverflow>0 || pPage->nFree>pPage->pBt->usableSize*2/3 ){
- rc = balance_nonroot(pPage);
- }
- }
- return rc;
-}
-
-/*
-** This routine checks all cursors that point to table pgnoRoot.
-** If any of those cursors other than pExclude were opened with
-** wrFlag==0 then this routine returns SQLITE_LOCKED. If all
-** cursors that point to pgnoRoot were opened with wrFlag==1
-** then this routine returns SQLITE_OK.
-**
-** In addition to checking for read-locks (where a read-lock
-** means a cursor opened with wrFlag==0) this routine also moves
-** all cursors other than pExclude so that they are pointing to the
-** first Cell on root page. This is necessary because an insert
-** or delete might change the number of cells on a page or delete
-** a page entirely and we do not want to leave any cursors
-** pointing to non-existant pages or cells.
-*/
-static int checkReadLocks(Btree *pBt, Pgno pgnoRoot, BtCursor *pExclude){
- BtCursor *p;
- for(p=pBt->pCursor; p; p=p->pNext){
- if( p->pgnoRoot!=pgnoRoot || p==pExclude ) continue;
- if( p->wrFlag==0 ) return SQLITE_LOCKED;
- if( p->pPage->pgno!=p->pgnoRoot ){
- moveToRoot(p);
- }
- }
- return SQLITE_OK;
-}
-
-/*
-** Insert a new record into the BTree. The key is given by (pKey,nKey)
-** and the data is given by (pData,nData). The cursor is used only to
-** define what table the record should be inserted into. The cursor
-** is left pointing at a random location.
-**
-** For an INTKEY table, only the nKey value of the key is used. pKey is
-** ignored. For a ZERODATA table, the pData and nData are both ignored.
-*/
-int sqlite3BtreeInsert(
- BtCursor *pCur, /* Insert data into the table of this cursor */
- const void *pKey, i64 nKey, /* The key of the new record */
- const void *pData, int nData /* The data of the new record */
-){
- int rc;
- int loc;
- int szNew;
- MemPage *pPage;
- Btree *pBt = pCur->pBt;
- unsigned char *oldCell;
- unsigned char *newCell = 0;
-
- if( pCur->status ){
- return pCur->status; /* A rollback destroyed this cursor */
- }
- if( pBt->inTrans!=TRANS_WRITE ){
- /* Must start a transaction before doing an insert */
- return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
- }
- assert( !pBt->readOnly );
- if( !pCur->wrFlag ){
- return SQLITE_PERM; /* Cursor not open for writing */
- }
- if( checkReadLocks(pBt, pCur->pgnoRoot, pCur) ){
- return SQLITE_LOCKED; /* The table pCur points to has a read lock */
- }
- rc = sqlite3BtreeMoveto(pCur, pKey, nKey, &loc);
- if( rc ) return rc;
- pPage = pCur->pPage;
- assert( pPage->intKey || nKey>=0 );
- assert( pPage->leaf || !pPage->leafData );
- TRACE(("INSERT: table=%d nkey=%lld ndata=%d page=%d %s\n",
- pCur->pgnoRoot, nKey, nData, pPage->pgno,
- loc==0 ? "overwrite" : "new entry"));
- assert( pPage->isInit );
- rc = sqlite3pager_write(pPage->aData);
- if( rc ) return rc;
- newCell = sqliteMallocRaw( MX_CELL_SIZE(pBt) );
- if( newCell==0 ) return SQLITE_NOMEM;
- rc = fillInCell(pPage, newCell, pKey, nKey, pData, nData, &szNew);
- if( rc ) goto end_insert;
- assert( szNew==cellSizePtr(pPage, newCell) );
- assert( szNew<=MX_CELL_SIZE(pBt) );
- if( loc==0 && pCur->isValid ){
- int szOld;
- assert( pCur->idx>=0 && pCur->idx<pPage->nCell );
- oldCell = findCell(pPage, pCur->idx);
- if( !pPage->leaf ){
- memcpy(newCell, oldCell, 4);
- }
- szOld = cellSizePtr(pPage, oldCell);
- rc = clearCell(pPage, oldCell);
- if( rc ) goto end_insert;
- dropCell(pPage, pCur->idx, szOld);
- }else if( loc<0 && pPage->nCell>0 ){
- assert( pPage->leaf );
- pCur->idx++;
- pCur->info.nSize = 0;
- }else{
- assert( pPage->leaf );
- }
- insertCell(pPage, pCur->idx, newCell, szNew, 0);
- rc = balance(pPage);
- /* sqlite3BtreePageDump(pCur->pBt, pCur->pgnoRoot, 1); */
- /* fflush(stdout); */
- moveToRoot(pCur);
-end_insert:
- sqliteFree(newCell);
- return rc;
-}
-
-/*
-** Delete the entry that the cursor is pointing to. The cursor
-** is left pointing at a random location.
-*/
-int sqlite3BtreeDelete(BtCursor *pCur){
- MemPage *pPage = pCur->pPage;
- unsigned char *pCell;
- int rc;
- Pgno pgnoChild = 0;
- Btree *pBt = pCur->pBt;
-
- assert( pPage->isInit );
- if( pCur->status ){
- return pCur->status; /* A rollback destroyed this cursor */
- }
- if( pBt->inTrans!=TRANS_WRITE ){
- /* Must start a transaction before doing a delete */
- return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
- }
- assert( !pBt->readOnly );
- if( pCur->idx >= pPage->nCell ){
- return SQLITE_ERROR; /* The cursor is not pointing to anything */
- }
- if( !pCur->wrFlag ){
- return SQLITE_PERM; /* Did not open this cursor for writing */
- }
- if( checkReadLocks(pBt, pCur->pgnoRoot, pCur) ){
- return SQLITE_LOCKED; /* The table pCur points to has a read lock */
- }
- rc = sqlite3pager_write(pPage->aData);
- if( rc ) return rc;
- pCell = findCell(pPage, pCur->idx);
- if( !pPage->leaf ){
- pgnoChild = get4byte(pCell);
- }
- clearCell(pPage, pCell);
- if( !pPage->leaf ){
- /*
- ** The entry we are about to delete is not a leaf so if we do not
- ** do something we will leave a hole on an internal page.
- ** We have to fill the hole by moving in a cell from a leaf. The
- ** next Cell after the one to be deleted is guaranteed to exist and
- ** to be a leaf so we can use it.
- */
- BtCursor leafCur;
- unsigned char *pNext;
- int szNext;
- int notUsed;
- unsigned char *tempCell;
- assert( !pPage->leafData );
- getTempCursor(pCur, &leafCur);
- rc = sqlite3BtreeNext(&leafCur, &notUsed);
- if( rc!=SQLITE_OK ){
- if( rc!=SQLITE_NOMEM ){
- rc = SQLITE_CORRUPT; /* bkpt-CORRUPT */
- }
- return rc;
- }
- rc = sqlite3pager_write(leafCur.pPage->aData);
- if( rc ) return rc;
- TRACE(("DELETE: table=%d delete internal from %d replace from leaf %d\n",
- pCur->pgnoRoot, pPage->pgno, leafCur.pPage->pgno));
- dropCell(pPage, pCur->idx, cellSizePtr(pPage, pCell));
- pNext = findCell(leafCur.pPage, leafCur.idx);
- szNext = cellSizePtr(leafCur.pPage, pNext);
- assert( MX_CELL_SIZE(pBt)>=szNext+4 );
- tempCell = sqliteMallocRaw( MX_CELL_SIZE(pBt) );
- if( tempCell==0 ) return SQLITE_NOMEM;
- insertCell(pPage, pCur->idx, pNext-4, szNext+4, tempCell);
- put4byte(findOverflowCell(pPage, pCur->idx), pgnoChild);
- rc = balance(pPage);
- sqliteFree(tempCell);
- if( rc ) return rc;
- dropCell(leafCur.pPage, leafCur.idx, szNext);
- rc = balance(leafCur.pPage);
- releaseTempCursor(&leafCur);
- }else{
- TRACE(("DELETE: table=%d delete from leaf %d\n",
- pCur->pgnoRoot, pPage->pgno));
- dropCell(pPage, pCur->idx, cellSizePtr(pPage, pCell));
- rc = balance(pPage);
- }
- moveToRoot(pCur);
- return rc;
-}
-
-/*
-** Create a new BTree table. Write into *piTable the page
-** number for the root page of the new table.
-**
-** The type of type is determined by the flags parameter. Only the
-** following values of flags are currently in use. Other values for
-** flags might not work:
-**
-** BTREE_INTKEY|BTREE_LEAFDATA Used for SQL tables with rowid keys
-** BTREE_ZERODATA Used for SQL indices
-*/
-int sqlite3BtreeCreateTable(Btree *pBt, int *piTable, int flags){
- MemPage *pRoot;
- Pgno pgnoRoot;
- int rc;
- if( pBt->inTrans!=TRANS_WRITE ){
- /* Must start a transaction first */
- return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
- }
- if( pBt->readOnly ){
- return SQLITE_READONLY;
- }
- rc = allocatePage(pBt, &pRoot, &pgnoRoot, 1);
- if( rc ) return rc;
- assert( sqlite3pager_iswriteable(pRoot->aData) );
- zeroPage(pRoot, flags | PTF_LEAF);
- sqlite3pager_unref(pRoot->aData);
- *piTable = (int)pgnoRoot;
- return SQLITE_OK;
-}
-
-/*
-** Erase the given database page and all its children. Return
-** the page to the freelist.
-*/
-static int clearDatabasePage(
- Btree *pBt, /* The BTree that contains the table */
- Pgno pgno, /* Page number to clear */
- MemPage *pParent, /* Parent page. NULL for the root */
- int freePageFlag /* Deallocate page if true */
-){
- MemPage *pPage;
- int rc;
- unsigned char *pCell;
- int i;
-
- rc = getAndInitPage(pBt, pgno, &pPage, pParent);
- if( rc ) return rc;
- rc = sqlite3pager_write(pPage->aData);
- if( rc ) return rc;
- for(i=0; i<pPage->nCell; i++){
- pCell = findCell(pPage, i);
- if( !pPage->leaf ){
- rc = clearDatabasePage(pBt, get4byte(pCell), pPage->pParent, 1);
- if( rc ) return rc;
- }
- rc = clearCell(pPage, pCell);
- if( rc ) return rc;
- }
- if( !pPage->leaf ){
- rc = clearDatabasePage(pBt, get4byte(&pPage->aData[8]), pPage->pParent, 1);
- if( rc ) return rc;
- }
- if( freePageFlag ){
- rc = freePage(pPage);
- }else{
- zeroPage(pPage, pPage->aData[0] | PTF_LEAF);
- }
- releasePage(pPage);
- return rc;
-}
-
-/*
-** Delete all information from a single table in the database. iTable is
-** the page number of the root of the table. After this routine returns,
-** the root page is empty, but still exists.
-**
-** This routine will fail with SQLITE_LOCKED if there are any open
-** read cursors on the table. Open write cursors are moved to the
-** root of the table.
-*/
-int sqlite3BtreeClearTable(Btree *pBt, int iTable){
- int rc;
- BtCursor *pCur;
- if( pBt->inTrans!=TRANS_WRITE ){
- return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
- }
- for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
- if( pCur->pgnoRoot==(Pgno)iTable ){
- if( pCur->wrFlag==0 ) return SQLITE_LOCKED;
- moveToRoot(pCur);
- }
- }
- rc = clearDatabasePage(pBt, (Pgno)iTable, 0, 0);
- if( rc ){
- sqlite3BtreeRollback(pBt);
- }
- return rc;
-}
-
-/*
-** Erase all information in a table and add the root of the table to
-** the freelist. Except, the root of the principle table (the one on
-** page 1) is never added to the freelist.
-**
-** This routine will fail with SQLITE_LOCKED if there are any open
-** cursors on the table.
-*/
-int sqlite3BtreeDropTable(Btree *pBt, int iTable){
- int rc;
- MemPage *pPage;
- BtCursor *pCur;
- if( pBt->inTrans!=TRANS_WRITE ){
- return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
- }
- for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
- if( pCur->pgnoRoot==(Pgno)iTable ){
- return SQLITE_LOCKED; /* Cannot drop a table that has a cursor */
- }
- }
- rc = getPage(pBt, (Pgno)iTable, &pPage);
- if( rc ) return rc;
- rc = sqlite3BtreeClearTable(pBt, iTable);
- if( rc ) return rc;
- if( iTable>1 ){
- rc = freePage(pPage);
- }else{
- zeroPage(pPage, PTF_INTKEY|PTF_LEAF );
- }
- releasePage(pPage);
- return rc;
-}
-
-
-/*
-** Read the meta-information out of a database file. Meta[0]
-** is the number of free pages currently in the database. Meta[1]
-** through meta[15] are available for use by higher layers. Meta[0]
-** is read-only, the others are read/write.
-**
-** The schema layer numbers meta values differently. At the schema
-** layer (and the SetCookie and ReadCookie opcodes) the number of
-** free pages is not visible. So Cookie[0] is the same as Meta[1].
-*/
-int sqlite3BtreeGetMeta(Btree *pBt, int idx, u32 *pMeta){
- int rc;
- unsigned char *pP1;
-
- assert( idx>=0 && idx<=15 );
- rc = sqlite3pager_get(pBt->pPager, 1, (void**)&pP1);
- if( rc ) return rc;
- *pMeta = get4byte(&pP1[36 + idx*4]);
- sqlite3pager_unref(pP1);
-
- /* The current implementation is unable to handle writes to an autovacuumed
- ** database. So make such a database readonly. */
- if( idx==4 && *pMeta>0 ) pBt->readOnly = 1;
-
- return SQLITE_OK;
-}
-
-/*
-** Write meta-information back into the database. Meta[0] is
-** read-only and may not be written.
-*/
-int sqlite3BtreeUpdateMeta(Btree *pBt, int idx, u32 iMeta){
- unsigned char *pP1;
- int rc;
- assert( idx>=1 && idx<=15 );
- if( pBt->inTrans!=TRANS_WRITE ){
- return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
- }
- assert( pBt->pPage1!=0 );
- pP1 = pBt->pPage1->aData;
- rc = sqlite3pager_write(pP1);
- if( rc ) return rc;
- put4byte(&pP1[36 + idx*4], iMeta);
- return SQLITE_OK;
-}
-
-/*
-** Return the flag byte at the beginning of the page that the cursor
-** is currently pointing to.
-*/
-int sqlite3BtreeFlags(BtCursor *pCur){
- MemPage *pPage = pCur->pPage;
- return pPage ? pPage->aData[pPage->hdrOffset] : 0;
-}
-
-/*
-** Print a disassembly of the given page on standard output. This routine
-** is used for debugging and testing only.
-*/
-#ifdef SQLITE_TEST
-int sqlite3BtreePageDump(Btree *pBt, int pgno, int recursive){
- int rc;
- MemPage *pPage;
- int i, j, c;
- int nFree;
- u16 idx;
- int hdr;
- int nCell;
- int isInit;
- unsigned char *data;
- char range[20];
- unsigned char payload[20];
-
- rc = getPage(pBt, (Pgno)pgno, &pPage);
- isInit = pPage->isInit;
- if( pPage->isInit==0 ){
- initPage(pPage, 0);
- }
- if( rc ){
- return rc;
- }
- hdr = pPage->hdrOffset;
- data = pPage->aData;
- c = data[hdr];
- pPage->intKey = (c & (PTF_INTKEY|PTF_LEAFDATA))!=0;
- pPage->zeroData = (c & PTF_ZERODATA)!=0;
- pPage->leafData = (c & PTF_LEAFDATA)!=0;
- pPage->leaf = (c & PTF_LEAF)!=0;
- pPage->hasData = !(pPage->zeroData || (!pPage->leaf && pPage->leafData));
- nCell = get2byte(&data[hdr+3]);
- sqlite3DebugPrintf("PAGE %d: flags=0x%02x frag=%d parent=%d\n", pgno,
- data[hdr], data[hdr+7],
- (pPage->isInit && pPage->pParent) ? pPage->pParent->pgno : 0);
- assert( hdr == (pgno==1 ? 100 : 0) );
- idx = hdr + 12 - pPage->leaf*4;
- for(i=0; i<nCell; i++){
- CellInfo info;
- Pgno child;
- unsigned char *pCell;
- int sz;
- int addr;
-
- addr = get2byte(&data[idx + 2*i]);
- pCell = &data[addr];
- parseCellPtr(pPage, pCell, &info);
- sz = info.nSize;
- sprintf(range,"%d..%d", addr, addr+sz-1);
- if( pPage->leaf ){
- child = 0;
- }else{
- child = get4byte(pCell);
- }
- sz = info.nData;
- if( !pPage->intKey ) sz += info.nKey;
- if( sz>sizeof(payload)-1 ) sz = sizeof(payload)-1;
- memcpy(payload, &pCell[info.nHeader], sz);
- for(j=0; j<sz; j++){
- if( payload[j]<0x20 || payload[j]>0x7f ) payload[j] = '.';
- }
- payload[sz] = 0;
- sqlite3DebugPrintf(
- "cell %2d: i=%-10s chld=%-4d nk=%-4lld nd=%-4d payload=%s\n",
- i, range, child, info.nKey, info.nData, payload
- );
- }
- if( !pPage->leaf ){
- sqlite3DebugPrintf("right_child: %d\n", get4byte(&data[hdr+8]));
- }
- nFree = 0;
- i = 0;
- idx = get2byte(&data[hdr+1]);
- while( idx>0 && idx<pPage->pBt->usableSize ){
- int sz = get2byte(&data[idx+2]);
- sprintf(range,"%d..%d", idx, idx+sz-1);
- nFree += sz;
- sqlite3DebugPrintf("freeblock %2d: i=%-10s size=%-4d total=%d\n",
- i, range, sz, nFree);
- idx = get2byte(&data[idx]);
- i++;
- }
- if( idx!=0 ){
- sqlite3DebugPrintf("ERROR: next freeblock index out of range: %d\n", idx);
- }
- if( recursive && !pPage->leaf ){
- for(i=0; i<nCell; i++){
- unsigned char *pCell = findCell(pPage, i);
- sqlite3BtreePageDump(pBt, get4byte(pCell), 1);
- idx = get2byte(pCell);
- }
- sqlite3BtreePageDump(pBt, get4byte(&data[hdr+8]), 1);
- }
- pPage->isInit = isInit;
- sqlite3pager_unref(data);
- fflush(stdout);
- return SQLITE_OK;
-}
-#endif
-
-#ifdef SQLITE_TEST
-/*
-** Fill aResult[] with information about the entry and page that the
-** cursor is pointing to.
-**
-** aResult[0] = The page number
-** aResult[1] = The entry number
-** aResult[2] = Total number of entries on this page
-** aResult[3] = Cell size (local payload + header)
-** aResult[4] = Number of free bytes on this page
-** aResult[5] = Number of free blocks on the page
-** aResult[6] = Total payload size (local + overflow)
-** aResult[7] = Header size in bytes
-** aResult[8] = Local payload size
-** aResult[9] = Parent page number
-**
-** This routine is used for testing and debugging only.
-*/
-int sqlite3BtreeCursorInfo(BtCursor *pCur, int *aResult, int upCnt){
- int cnt, idx;
- MemPage *pPage = pCur->pPage;
- BtCursor tmpCur;
-
- pageIntegrity(pPage);
- assert( pPage->isInit );
- getTempCursor(pCur, &tmpCur);
- while( upCnt-- ){
- moveToParent(&tmpCur);
- }
- pPage = tmpCur.pPage;
- pageIntegrity(pPage);
- aResult[0] = sqlite3pager_pagenumber(pPage->aData);
- assert( aResult[0]==pPage->pgno );
- aResult[1] = tmpCur.idx;
- aResult[2] = pPage->nCell;
- if( tmpCur.idx>=0 && tmpCur.idx<pPage->nCell ){
- getCellInfo(&tmpCur);
- aResult[3] = tmpCur.info.nSize;
- aResult[6] = tmpCur.info.nData;
- aResult[7] = tmpCur.info.nHeader;
- aResult[8] = tmpCur.info.nLocal;
- }else{
- aResult[3] = 0;
- aResult[6] = 0;
- aResult[7] = 0;
- aResult[8] = 0;
- }
- aResult[4] = pPage->nFree;
- cnt = 0;
- idx = get2byte(&pPage->aData[pPage->hdrOffset+1]);
- while( idx>0 && idx<pPage->pBt->usableSize ){
- cnt++;
- idx = get2byte(&pPage->aData[idx]);
- }
- aResult[5] = cnt;
- if( pPage->pParent==0 || isRootPage(pPage) ){
- aResult[9] = 0;
- }else{
- aResult[9] = pPage->pParent->pgno;
- }
- releaseTempCursor(&tmpCur);
- return SQLITE_OK;
-}
-#endif
-
-/*
-** Return the pager associated with a BTree. This routine is used for
-** testing and debugging only.
-*/
-Pager *sqlite3BtreePager(Btree *pBt){
- return pBt->pPager;
-}
-
-/*
-** This structure is passed around through all the sanity checking routines
-** in order to keep track of some global state information.
-*/
-typedef struct IntegrityCk IntegrityCk;
-struct IntegrityCk {
- Btree *pBt; /* The tree being checked out */
- Pager *pPager; /* The associated pager. Also accessible by pBt->pPager */
- int nPage; /* Number of pages in the database */
- int *anRef; /* Number of times each page is referenced */
- char *zErrMsg; /* An error message. NULL of no errors seen. */
-};
-
-/*
-** Append a message to the error message string.
-*/
-static void checkAppendMsg(
- IntegrityCk *pCheck,
- char *zMsg1,
- const char *zFormat,
- ...
-){
- va_list ap;
- char *zMsg2;
- va_start(ap, zFormat);
- zMsg2 = sqlite3VMPrintf(zFormat, ap);
- va_end(ap);
- if( zMsg1==0 ) zMsg1 = "";
- if( pCheck->zErrMsg ){
- char *zOld = pCheck->zErrMsg;
- pCheck->zErrMsg = 0;
- sqlite3SetString(&pCheck->zErrMsg, zOld, "\n", zMsg1, zMsg2, (char*)0);
- sqliteFree(zOld);
- }else{
- sqlite3SetString(&pCheck->zErrMsg, zMsg1, zMsg2, (char*)0);
- }
- sqliteFree(zMsg2);
-}
-
-/*
-** Add 1 to the reference count for page iPage. If this is the second
-** reference to the page, add an error message to pCheck->zErrMsg.
-** Return 1 if there are 2 ore more references to the page and 0 if
-** if this is the first reference to the page.
-**
-** Also check that the page number is in bounds.
-*/
-static int checkRef(IntegrityCk *pCheck, int iPage, char *zContext){
- if( iPage==0 ) return 1;
- if( iPage>pCheck->nPage || iPage<0 ){
- checkAppendMsg(pCheck, zContext, "invalid page number %d", iPage);
- return 1;
- }
- if( pCheck->anRef[iPage]==1 ){
- checkAppendMsg(pCheck, zContext, "2nd reference to page %d", iPage);
- return 1;
- }
- return (pCheck->anRef[iPage]++)>1;
-}
-
-/*
-** Check the integrity of the freelist or of an overflow page list.
-** Verify that the number of pages on the list is N.
-*/
-static void checkList(
- IntegrityCk *pCheck, /* Integrity checking context */
- int isFreeList, /* True for a freelist. False for overflow page list */
- int iPage, /* Page number for first page in the list */
- int N, /* Expected number of pages in the list */
- char *zContext /* Context for error messages */
-){
- int i;
- int expected = N;
- int iFirst = iPage;
- while( N-- > 0 ){
- unsigned char *pOvfl;
- if( iPage<1 ){
- checkAppendMsg(pCheck, zContext,
- "%d of %d pages missing from overflow list starting at %d",
- N+1, expected, iFirst);
- break;
- }
- if( checkRef(pCheck, iPage, zContext) ) break;
- if( sqlite3pager_get(pCheck->pPager, (Pgno)iPage, (void**)&pOvfl) ){
- checkAppendMsg(pCheck, zContext, "failed to get page %d", iPage);
- break;
- }
- if( isFreeList ){
- int n = get4byte(&pOvfl[4]);
- if( n>pCheck->pBt->usableSize/4-8 ){
- checkAppendMsg(pCheck, zContext,
- "freelist leaf count too big on page %d", iPage);
- N--;
- }else{
- for(i=0; i<n; i++){
- checkRef(pCheck, get4byte(&pOvfl[8+i*4]), zContext);
- }
- N -= n;
- }
- }
- iPage = get4byte(pOvfl);
- sqlite3pager_unref(pOvfl);
- }
-}
-
-/*
-** Do various sanity checks on a single page of a tree. Return
-** the tree depth. Root pages return 0. Parents of root pages
-** return 1, and so forth.
-**
-** These checks are done:
-**
-** 1. Make sure that cells and freeblocks do not overlap
-** but combine to completely cover the page.
-** NO 2. Make sure cell keys are in order.
-** NO 3. Make sure no key is less than or equal to zLowerBound.
-** NO 4. Make sure no key is greater than or equal to zUpperBound.
-** 5. Check the integrity of overflow pages.
-** 6. Recursively call checkTreePage on all children.
-** 7. Verify that the depth of all children is the same.
-** 8. Make sure this page is at least 33% full or else it is
-** the root of the tree.
-*/
-static int checkTreePage(
- IntegrityCk *pCheck, /* Context for the sanity check */
- int iPage, /* Page number of the page to check */
- MemPage *pParent, /* Parent page */
- char *zParentContext, /* Parent context */
- char *zLowerBound, /* All keys should be greater than this, if not NULL */
- int nLower, /* Number of characters in zLowerBound */
- char *zUpperBound, /* All keys should be less than this, if not NULL */
- int nUpper /* Number of characters in zUpperBound */
-){
- MemPage *pPage;
- int i, rc, depth, d2, pgno, cnt;
- int hdr, cellStart;
- int nCell;
- u8 *data;
- BtCursor cur;
- Btree *pBt;
- int maxLocal, usableSize;
- char zContext[100];
- char *hit;
-
- /* Check that the page exists
- */
- cur.pBt = pBt = pCheck->pBt;
- usableSize = pBt->usableSize;
- if( iPage==0 ) return 0;
- if( checkRef(pCheck, iPage, zParentContext) ) return 0;
- if( (rc = getPage(pBt, (Pgno)iPage, &pPage))!=0 ){
- checkAppendMsg(pCheck, zContext,
- "unable to get the page. error code=%d", rc);
- return 0;
- }
- maxLocal = pPage->leafData ? pBt->maxLeaf : pBt->maxLocal;
- if( (rc = initPage(pPage, pParent))!=0 ){
- checkAppendMsg(pCheck, zContext, "initPage() returns error code %d", rc);
- releasePage(pPage);
- return 0;
- }
-
- /* Check out all the cells.
- */
- depth = 0;
- cur.pPage = pPage;
- for(i=0; i<pPage->nCell; i++){
- u8 *pCell;
- int sz;
- CellInfo info;
-
- /* Check payload overflow pages
- */
- sprintf(zContext, "On tree page %d cell %d: ", iPage, i);
- pCell = findCell(pPage,i);
- parseCellPtr(pPage, pCell, &info);
- sz = info.nData;
- if( !pPage->intKey ) sz += info.nKey;
- if( sz>info.nLocal ){
- int nPage = (sz - info.nLocal + usableSize - 5)/(usableSize - 4);
- checkList(pCheck, 0, get4byte(&pCell[info.iOverflow]),nPage,zContext);
- }
-
- /* Check sanity of left child page.
- */
- if( !pPage->leaf ){
- pgno = get4byte(pCell);
- d2 = checkTreePage(pCheck,pgno,pPage,zContext,0,0,0,0);
- if( i>0 && d2!=depth ){
- checkAppendMsg(pCheck, zContext, "Child page depth differs");
- }
- depth = d2;
- }
- }
- if( !pPage->leaf ){
- pgno = get4byte(&pPage->aData[pPage->hdrOffset+8]);
- sprintf(zContext, "On page %d at right child: ", iPage);
- checkTreePage(pCheck, pgno, pPage, zContext,0,0,0,0);
- }
-
- /* Check for complete coverage of the page
- */
- data = pPage->aData;
- hdr = pPage->hdrOffset;
- hit = sqliteMalloc( usableSize );
- if( hit ){
- memset(hit, 1, get2byte(&data[hdr+5]));
- nCell = get2byte(&data[hdr+3]);
- cellStart = hdr + 12 - 4*pPage->leaf;
- for(i=0; i<nCell; i++){
- int pc = get2byte(&data[cellStart+i*2]);
- int size = cellSizePtr(pPage, &data[pc]);
- int j;
- for(j=pc+size-1; j>=pc; j--) hit[j]++;
- }
- for(cnt=0, i=get2byte(&data[hdr+1]); i>0 && i<usableSize && cnt<10000;
- cnt++){
- int size = get2byte(&data[i+2]);
- int j;
- for(j=i+size-1; j>=i; j--) hit[j]++;
- i = get2byte(&data[i]);
- }
- for(i=cnt=0; i<usableSize; i++){
- if( hit[i]==0 ){
- cnt++;
- }else if( hit[i]>1 ){
- checkAppendMsg(pCheck, 0,
- "Multiple uses for byte %d of page %d", i, iPage);
- break;
- }
- }
- if( cnt!=data[hdr+7] ){
- checkAppendMsg(pCheck, 0,
- "Fragmented space is %d byte reported as %d on page %d",
- cnt, data[hdr+7], iPage);
- }
- }
- sqliteFree(hit);
-
- releasePage(pPage);
- return depth+1;
-}
-
-/*
-** This routine does a complete check of the given BTree file. aRoot[] is
-** an array of pages numbers were each page number is the root page of
-** a table. nRoot is the number of entries in aRoot.
-**
-** If everything checks out, this routine returns NULL. If something is
-** amiss, an error message is written into memory obtained from malloc()
-** and a pointer to that error message is returned. The calling function
-** is responsible for freeing the error message when it is done.
-*/
-char *sqlite3BtreeIntegrityCheck(Btree *pBt, int *aRoot, int nRoot){
- int i;
- int nRef;
- IntegrityCk sCheck;
-
- nRef = *sqlite3pager_stats(pBt->pPager);
- if( lockBtree(pBt)!=SQLITE_OK ){
- return sqliteStrDup("Unable to acquire a read lock on the database");
- }
- sCheck.pBt = pBt;
- sCheck.pPager = pBt->pPager;
- sCheck.nPage = sqlite3pager_pagecount(sCheck.pPager);
- if( sCheck.nPage==0 ){
- unlockBtreeIfUnused(pBt);
- return 0;
- }
- sCheck.anRef = sqliteMallocRaw( (sCheck.nPage+1)*sizeof(sCheck.anRef[0]) );
- for(i=0; i<=sCheck.nPage; i++){ sCheck.anRef[i] = 0; }
- i = PENDING_BYTE/pBt->pageSize + 1;
- if( i<=sCheck.nPage ){
- sCheck.anRef[i] = 1;
- }
- sCheck.zErrMsg = 0;
-
- /* Check the integrity of the freelist
- */
- checkList(&sCheck, 1, get4byte(&pBt->pPage1->aData[32]),
- get4byte(&pBt->pPage1->aData[36]), "Main freelist: ");
-
- /* Check all the tables.
- */
- for(i=0; i<nRoot; i++){
- if( aRoot[i]==0 ) continue;
- checkTreePage(&sCheck, aRoot[i], 0, "List of tree roots: ", 0,0,0,0);
- }
-
- /* Make sure every page in the file is referenced
- */
- for(i=1; i<=sCheck.nPage; i++){
- if( sCheck.anRef[i]==0 ){
- checkAppendMsg(&sCheck, 0, "Page %d is never used", i);
- }
- }
-
- /* Make sure this analysis did not leave any unref() pages
- */
- unlockBtreeIfUnused(pBt);
- if( nRef != *sqlite3pager_stats(pBt->pPager) ){
- checkAppendMsg(&sCheck, 0,
- "Outstanding page count goes from %d to %d during this analysis",
- nRef, *sqlite3pager_stats(pBt->pPager)
- );
- }
-
- /* Clean up and report errors.
- */
- sqliteFree(sCheck.anRef);
- return sCheck.zErrMsg;
-}
-
-/*
-** Return the full pathname of the underlying database file.
-*/
-const char *sqlite3BtreeGetFilename(Btree *pBt){
- assert( pBt->pPager!=0 );
- return sqlite3pager_filename(pBt->pPager);
-}
-
-/*
-** Return the pathname of the directory that contains the database file.
-*/
-const char *sqlite3BtreeGetDirname(Btree *pBt){
- assert( pBt->pPager!=0 );
- return sqlite3pager_dirname(pBt->pPager);
-}
-
-/*
-** Return the pathname of the journal file for this database. The return
-** value of this routine is the same regardless of whether the journal file
-** has been created or not.
-*/
-const char *sqlite3BtreeGetJournalname(Btree *pBt){
- assert( pBt->pPager!=0 );
- return sqlite3pager_journalname(pBt->pPager);
-}
-
-/*
-** Copy the complete content of pBtFrom into pBtTo. A transaction
-** must be active for both files.
-**
-** The size of file pBtFrom may be reduced by this operation.
-** If anything goes wrong, the transaction on pBtFrom is rolled back.
-*/
-int sqlite3BtreeCopyFile(Btree *pBtTo, Btree *pBtFrom){
- int rc = SQLITE_OK;
- Pgno i, nPage, nToPage;
-
- if( pBtTo->inTrans!=TRANS_WRITE || pBtFrom->inTrans!=TRANS_WRITE ){
- return SQLITE_ERROR;
- }
- if( pBtTo->pCursor ) return SQLITE_BUSY;
- nToPage = sqlite3pager_pagecount(pBtTo->pPager);
- nPage = sqlite3pager_pagecount(pBtFrom->pPager);
- for(i=1; rc==SQLITE_OK && i<=nPage; i++){
- void *pPage;
- rc = sqlite3pager_get(pBtFrom->pPager, i, &pPage);
- if( rc ) break;
- rc = sqlite3pager_overwrite(pBtTo->pPager, i, pPage);
- if( rc ) break;
- sqlite3pager_unref(pPage);
- }
- for(i=nPage+1; rc==SQLITE_OK && i<=nToPage; i++){
- void *pPage;
- rc = sqlite3pager_get(pBtTo->pPager, i, &pPage);
- if( rc ) break;
- rc = sqlite3pager_write(pPage);
- sqlite3pager_unref(pPage);
- sqlite3pager_dont_write(pBtTo->pPager, i);
- }
- if( !rc && nPage<nToPage ){
- rc = sqlite3pager_truncate(pBtTo->pPager, nPage);
- }
- if( rc ){
- sqlite3BtreeRollback(pBtTo);
- }
- return rc;
-}
-
-/*
-** Return non-zero if a transaction is active.
-*/
-int sqlite3BtreeIsInTrans(Btree *pBt){
- return (pBt && (pBt->inTrans==TRANS_WRITE));
-}
-
-/*
-** Return non-zero if a statement transaction is active.
-*/
-int sqlite3BtreeIsInStmt(Btree *pBt){
- return (pBt && pBt->inStmt);
-}
-
-/*
-** This call is a no-op if no write-transaction is currently active on pBt.
-**
-** Otherwise, sync the database file for the btree pBt. zMaster points to
-** the name of a master journal file that should be written into the
-** individual journal file, or is NULL, indicating no master journal file
-** (single database transaction).
-**
-** When this is called, the master journal should already have been
-** created, populated with this journal pointer and synced to disk.
-**
-** Once this is routine has returned, the only thing required to commit
-** the write-transaction for this database file is to delete the journal.
-*/
-int sqlite3BtreeSync(Btree *pBt, const char *zMaster){
- if( pBt->inTrans==TRANS_WRITE ){
- return sqlite3pager_sync(pBt->pPager, zMaster);
- }
- return SQLITE_OK;
-}