Annotation of embedaddon/php/ext/sqlite/libsqlite/src/btree.c, revision 1.1.1.1

1.1       misho       1: /*
                      2: ** 2001 September 15
                      3: **
                      4: ** The author disclaims copyright to this source code.  In place of
                      5: ** a legal notice, here is a blessing:
                      6: **
                      7: **    May you do good and not evil.
                      8: **    May you find forgiveness for yourself and forgive others.
                      9: **    May you share freely, never taking more than you give.
                     10: **
                     11: *************************************************************************
                     12: ** $Id: btree.c 195361 2005-09-07 15:11:33Z iliaa $
                     13: **
                     14: ** This file implements a external (disk-based) database using BTrees.
                     15: ** For a detailed discussion of BTrees, refer to
                     16: **
                     17: **     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
                     18: **     "Sorting And Searching", pages 473-480. Addison-Wesley
                     19: **     Publishing Company, Reading, Massachusetts.
                     20: **
                     21: ** The basic idea is that each page of the file contains N database
                     22: ** entries and N+1 pointers to subpages.
                     23: **
                     24: **   ----------------------------------------------------------------
                     25: **   |  Ptr(0) | Key(0) | Ptr(1) | Key(1) | ... | Key(N) | Ptr(N+1) |
                     26: **   ----------------------------------------------------------------
                     27: **
                     28: ** All of the keys on the page that Ptr(0) points to have values less
                     29: ** than Key(0).  All of the keys on page Ptr(1) and its subpages have
                     30: ** values greater than Key(0) and less than Key(1).  All of the keys
                     31: ** on Ptr(N+1) and its subpages have values greater than Key(N).  And
                     32: ** so forth.
                     33: **
                     34: ** Finding a particular key requires reading O(log(M)) pages from the 
                     35: ** disk where M is the number of entries in the tree.
                     36: **
                     37: ** In this implementation, a single file can hold one or more separate 
                     38: ** BTrees.  Each BTree is identified by the index of its root page.  The
                     39: ** key and data for any entry are combined to form the "payload".  Up to
                     40: ** MX_LOCAL_PAYLOAD bytes of payload can be carried directly on the
                     41: ** database page.  If the payload is larger than MX_LOCAL_PAYLOAD bytes
                     42: ** then surplus bytes are stored on overflow pages.  The payload for an
                     43: ** entry and the preceding pointer are combined to form a "Cell".  Each 
                     44: ** page has a small header which contains the Ptr(N+1) pointer.
                     45: **
                     46: ** The first page of the file contains a magic string used to verify that
                     47: ** the file really is a valid BTree database, a pointer to a list of unused
                     48: ** pages in the file, and some meta information.  The root of the first
                     49: ** BTree begins on page 2 of the file.  (Pages are numbered beginning with
                     50: ** 1, not 0.)  Thus a minimum database contains 2 pages.
                     51: */
                     52: #include "sqliteInt.h"
                     53: #include "pager.h"
                     54: #include "btree.h"
                     55: #include <assert.h>
                     56: 
                     57: /* Forward declarations */
                     58: static BtOps sqliteBtreeOps;
                     59: static BtCursorOps sqliteBtreeCursorOps;
                     60: 
                     61: /*
                     62: ** Macros used for byteswapping.  B is a pointer to the Btree
                     63: ** structure.  This is needed to access the Btree.needSwab boolean
                     64: ** in order to tell if byte swapping is needed or not.
                     65: ** X is an unsigned integer.  SWAB16 byte swaps a 16-bit integer.
                     66: ** SWAB32 byteswaps a 32-bit integer.
                     67: */
                     68: #define SWAB16(B,X)   ((B)->needSwab? swab16((u16)X) : ((u16)X))
                     69: #define SWAB32(B,X)   ((B)->needSwab? swab32(X) : (X))
                     70: #define SWAB_ADD(B,X,A) \
                     71:    if((B)->needSwab){ X=swab32(swab32(X)+A); }else{ X += (A); }
                     72: 
                     73: /*
                     74: ** The following global variable - available only if SQLITE_TEST is
                     75: ** defined - is used to determine whether new databases are created in
                     76: ** native byte order or in non-native byte order.  Non-native byte order
                     77: ** databases are created for testing purposes only.  Under normal operation,
                     78: ** only native byte-order databases should be created, but we should be
                     79: ** able to read or write existing databases regardless of the byteorder.
                     80: */
                     81: #ifdef SQLITE_TEST
                     82: int btree_native_byte_order = 1;
                     83: #else
                     84: # define btree_native_byte_order 1
                     85: #endif
                     86: 
                     87: /*
                     88: ** Forward declarations of structures used only in this file.
                     89: */
                     90: typedef struct PageOne PageOne;
                     91: typedef struct MemPage MemPage;
                     92: typedef struct PageHdr PageHdr;
                     93: typedef struct Cell Cell;
                     94: typedef struct CellHdr CellHdr;
                     95: typedef struct FreeBlk FreeBlk;
                     96: typedef struct OverflowPage OverflowPage;
                     97: typedef struct FreelistInfo FreelistInfo;
                     98: 
                     99: /*
                    100: ** All structures on a database page are aligned to 4-byte boundries.
                    101: ** This routine rounds up a number of bytes to the next multiple of 4.
                    102: **
                    103: ** This might need to change for computer architectures that require
                    104: ** and 8-byte alignment boundry for structures.
                    105: */
                    106: #define ROUNDUP(X)  ((X+3) & ~3)
                    107: 
                    108: /*
                    109: ** This is a magic string that appears at the beginning of every
                    110: ** SQLite database in order to identify the file as a real database.
                    111: */
                    112: static const char zMagicHeader[] = 
                    113:    "** This file contains an SQLite 2.1 database **";
                    114: #define MAGIC_SIZE (sizeof(zMagicHeader))
                    115: 
                    116: /*
                    117: ** This is a magic integer also used to test the integrity of the database
                    118: ** file.  This integer is used in addition to the string above so that
                    119: ** if the file is written on a little-endian architecture and read
                    120: ** on a big-endian architectures (or vice versa) we can detect the
                    121: ** problem.
                    122: **
                    123: ** The number used was obtained at random and has no special
                    124: ** significance other than the fact that it represents a different
                    125: ** integer on little-endian and big-endian machines.
                    126: */
                    127: #define MAGIC 0xdae37528
                    128: 
                    129: /*
                    130: ** The first page of the database file contains a magic header string
                    131: ** to identify the file as an SQLite database file.  It also contains
                    132: ** a pointer to the first free page of the file.  Page 2 contains the
                    133: ** root of the principle BTree.  The file might contain other BTrees
                    134: ** rooted on pages above 2.
                    135: **
                    136: ** The first page also contains SQLITE_N_BTREE_META integers that
                    137: ** can be used by higher-level routines.
                    138: **
                    139: ** Remember that pages are numbered beginning with 1.  (See pager.c
                    140: ** for additional information.)  Page 0 does not exist and a page
                    141: ** number of 0 is used to mean "no such page".
                    142: */
                    143: struct PageOne {
                    144:   char zMagic[MAGIC_SIZE]; /* String that identifies the file as a database */
                    145:   int iMagic;              /* Integer to verify correct byte order */
                    146:   Pgno freeList;           /* First free page in a list of all free pages */
                    147:   int nFree;               /* Number of pages on the free list */
                    148:   int aMeta[SQLITE_N_BTREE_META-1];  /* User defined integers */
                    149: };
                    150: 
                    151: /*
                    152: ** Each database page has a header that is an instance of this
                    153: ** structure.
                    154: **
                    155: ** PageHdr.firstFree is 0 if there is no free space on this page.
                    156: ** Otherwise, PageHdr.firstFree is the index in MemPage.u.aDisk[] of a 
                    157: ** FreeBlk structure that describes the first block of free space.  
                    158: ** All free space is defined by a linked list of FreeBlk structures.
                    159: **
                    160: ** Data is stored in a linked list of Cell structures.  PageHdr.firstCell
                    161: ** is the index into MemPage.u.aDisk[] of the first cell on the page.  The
                    162: ** Cells are kept in sorted order.
                    163: **
                    164: ** A Cell contains all information about a database entry and a pointer
                    165: ** to a child page that contains other entries less than itself.  In
                    166: ** other words, the i-th Cell contains both Ptr(i) and Key(i).  The
                    167: ** right-most pointer of the page is contained in PageHdr.rightChild.
                    168: */
                    169: struct PageHdr {
                    170:   Pgno rightChild;  /* Child page that comes after all cells on this page */
                    171:   u16 firstCell;    /* Index in MemPage.u.aDisk[] of the first cell */
                    172:   u16 firstFree;    /* Index in MemPage.u.aDisk[] of the first free block */
                    173: };
                    174: 
                    175: /*
                    176: ** Entries on a page of the database are called "Cells".  Each Cell
                    177: ** has a header and data.  This structure defines the header.  The
                    178: ** key and data (collectively the "payload") follow this header on
                    179: ** the database page.
                    180: **
                    181: ** A definition of the complete Cell structure is given below.  The
                    182: ** header for the cell must be defined first in order to do some
                    183: ** of the sizing #defines that follow.
                    184: */
                    185: struct CellHdr {
                    186:   Pgno leftChild; /* Child page that comes before this cell */
                    187:   u16 nKey;       /* Number of bytes in the key */
                    188:   u16 iNext;      /* Index in MemPage.u.aDisk[] of next cell in sorted order */
                    189:   u8 nKeyHi;      /* Upper 8 bits of key size for keys larger than 64K bytes */
                    190:   u8 nDataHi;     /* Upper 8 bits of data size when the size is more than 64K */
                    191:   u16 nData;      /* Number of bytes of data */
                    192: };
                    193: 
                    194: /*
                    195: ** The key and data size are split into a lower 16-bit segment and an
                    196: ** upper 8-bit segment in order to pack them together into a smaller
                    197: ** space.  The following macros reassembly a key or data size back
                    198: ** into an integer.
                    199: */
                    200: #define NKEY(b,h)  (SWAB16(b,h.nKey) + h.nKeyHi*65536)
                    201: #define NDATA(b,h) (SWAB16(b,h.nData) + h.nDataHi*65536)
                    202: 
                    203: /*
                    204: ** The minimum size of a complete Cell.  The Cell must contain a header
                    205: ** and at least 4 bytes of payload.
                    206: */
                    207: #define MIN_CELL_SIZE  (sizeof(CellHdr)+4)
                    208: 
                    209: /*
                    210: ** The maximum number of database entries that can be held in a single
                    211: ** page of the database. 
                    212: */
                    213: #define MX_CELL ((SQLITE_USABLE_SIZE-sizeof(PageHdr))/MIN_CELL_SIZE)
                    214: 
                    215: /*
                    216: ** The amount of usable space on a single page of the BTree.  This is the
                    217: ** page size minus the overhead of the page header.
                    218: */
                    219: #define USABLE_SPACE  (SQLITE_USABLE_SIZE - sizeof(PageHdr))
                    220: 
                    221: /*
                    222: ** The maximum amount of payload (in bytes) that can be stored locally for
                    223: ** a database entry.  If the entry contains more data than this, the
                    224: ** extra goes onto overflow pages.
                    225: **
                    226: ** This number is chosen so that at least 4 cells will fit on every page.
                    227: */
                    228: #define MX_LOCAL_PAYLOAD ((USABLE_SPACE/4-(sizeof(CellHdr)+sizeof(Pgno)))&~3)
                    229: 
                    230: /*
                    231: ** Data on a database page is stored as a linked list of Cell structures.
                    232: ** Both the key and the data are stored in aPayload[].  The key always comes
                    233: ** first.  The aPayload[] field grows as necessary to hold the key and data,
                    234: ** up to a maximum of MX_LOCAL_PAYLOAD bytes.  If the size of the key and
                    235: ** data combined exceeds MX_LOCAL_PAYLOAD bytes, then Cell.ovfl is the
                    236: ** page number of the first overflow page.
                    237: **
                    238: ** Though this structure is fixed in size, the Cell on the database
                    239: ** page varies in size.  Every cell has a CellHdr and at least 4 bytes
                    240: ** of payload space.  Additional payload bytes (up to the maximum of
                    241: ** MX_LOCAL_PAYLOAD) and the Cell.ovfl value are allocated only as
                    242: ** needed.
                    243: */
                    244: struct Cell {
                    245:   CellHdr h;                        /* The cell header */
                    246:   char aPayload[MX_LOCAL_PAYLOAD];  /* Key and data */
                    247:   Pgno ovfl;                        /* The first overflow page */
                    248: };
                    249: 
                    250: /*
                    251: ** Free space on a page is remembered using a linked list of the FreeBlk
                    252: ** structures.  Space on a database page is allocated in increments of
                    253: ** at least 4 bytes and is always aligned to a 4-byte boundry.  The
                    254: ** linked list of FreeBlks is always kept in order by address.
                    255: */
                    256: struct FreeBlk {
                    257:   u16 iSize;      /* Number of bytes in this block of free space */
                    258:   u16 iNext;      /* Index in MemPage.u.aDisk[] of the next free block */
                    259: };
                    260: 
                    261: /*
                    262: ** The number of bytes of payload that will fit on a single overflow page.
                    263: */
                    264: #define OVERFLOW_SIZE (SQLITE_USABLE_SIZE-sizeof(Pgno))
                    265: 
                    266: /*
                    267: ** When the key and data for a single entry in the BTree will not fit in
                    268: ** the MX_LOCAL_PAYLOAD bytes of space available on the database page,
                    269: ** then all extra bytes are written to a linked list of overflow pages.
                    270: ** Each overflow page is an instance of the following structure.
                    271: **
                    272: ** Unused pages in the database are also represented by instances of
                    273: ** the OverflowPage structure.  The PageOne.freeList field is the
                    274: ** page number of the first page in a linked list of unused database
                    275: ** pages.
                    276: */
                    277: struct OverflowPage {
                    278:   Pgno iNext;
                    279:   char aPayload[OVERFLOW_SIZE];
                    280: };
                    281: 
                    282: /*
                    283: ** The PageOne.freeList field points to a linked list of overflow pages
                    284: ** hold information about free pages.  The aPayload section of each
                    285: ** overflow page contains an instance of the following structure.  The
                    286: ** aFree[] array holds the page number of nFree unused pages in the disk
                    287: ** file.
                    288: */
                    289: struct FreelistInfo {
                    290:   int nFree;
                    291:   Pgno aFree[(OVERFLOW_SIZE-sizeof(int))/sizeof(Pgno)];
                    292: };
                    293: 
                    294: /*
                    295: ** For every page in the database file, an instance of the following structure
                    296: ** is stored in memory.  The u.aDisk[] array contains the raw bits read from
                    297: ** the disk.  The rest is auxiliary information held in memory only. The
                    298: ** auxiliary info is only valid for regular database pages - it is not
                    299: ** used for overflow pages and pages on the freelist.
                    300: **
                    301: ** Of particular interest in the auxiliary info is the apCell[] entry.  Each
                    302: ** apCell[] entry is a pointer to a Cell structure in u.aDisk[].  The cells are
                    303: ** put in this array so that they can be accessed in constant time, rather
                    304: ** than in linear time which would be needed if we had to walk the linked 
                    305: ** list on every access.
                    306: **
                    307: ** Note that apCell[] contains enough space to hold up to two more Cells
                    308: ** than can possibly fit on one page.  In the steady state, every apCell[]
                    309: ** points to memory inside u.aDisk[].  But in the middle of an insert
                    310: ** operation, some apCell[] entries may temporarily point to data space
                    311: ** outside of u.aDisk[].  This is a transient situation that is quickly
                    312: ** resolved.  But while it is happening, it is possible for a database
                    313: ** page to hold as many as two more cells than it might otherwise hold.
                    314: ** The extra two entries in apCell[] are an allowance for this situation.
                    315: **
                    316: ** The pParent field points back to the parent page.  This allows us to
                    317: ** walk up the BTree from any leaf to the root.  Care must be taken to
                    318: ** unref() the parent page pointer when this page is no longer referenced.
                    319: ** The pageDestructor() routine handles that chore.
                    320: */
                    321: struct MemPage {
                    322:   union u_page_data {
                    323:     char aDisk[SQLITE_PAGE_SIZE];  /* Page data stored on disk */
                    324:     PageHdr hdr;                   /* Overlay page header */
                    325:   } u;
                    326:   u8 isInit;                     /* True if auxiliary data is initialized */
                    327:   u8 idxShift;                   /* True if apCell[] indices have changed */
                    328:   u8 isOverfull;                 /* Some apCell[] points outside u.aDisk[] */
                    329:   MemPage *pParent;              /* The parent of this page.  NULL for root */
                    330:   int idxParent;                 /* Index in pParent->apCell[] of this node */
                    331:   int nFree;                     /* Number of free bytes in u.aDisk[] */
                    332:   int nCell;                     /* Number of entries on this page */
                    333:   Cell *apCell[MX_CELL+2];       /* All data entires in sorted order */
                    334: };
                    335: 
                    336: /*
                    337: ** The in-memory image of a disk page has the auxiliary information appended
                    338: ** to the end.  EXTRA_SIZE is the number of bytes of space needed to hold
                    339: ** that extra information.
                    340: */
                    341: #define EXTRA_SIZE (sizeof(MemPage)-sizeof(union u_page_data))
                    342: 
                    343: /*
                    344: ** Everything we need to know about an open database
                    345: */
                    346: struct Btree {
                    347:   BtOps *pOps;          /* Function table */
                    348:   Pager *pPager;        /* The page cache */
                    349:   BtCursor *pCursor;    /* A list of all open cursors */
                    350:   PageOne *page1;       /* First page of the database */
                    351:   u8 inTrans;           /* True if a transaction is in progress */
                    352:   u8 inCkpt;            /* True if there is a checkpoint on the transaction */
                    353:   u8 readOnly;          /* True if the underlying file is readonly */
                    354:   u8 needSwab;          /* Need to byte-swapping */
                    355: };
                    356: typedef Btree Bt;
                    357: 
                    358: /*
                    359: ** A cursor is a pointer to a particular entry in the BTree.
                    360: ** The entry is identified by its MemPage and the index in
                    361: ** MemPage.apCell[] of the entry.
                    362: */
                    363: struct BtCursor {
                    364:   BtCursorOps *pOps;        /* Function table */
                    365:   Btree *pBt;               /* The Btree to which this cursor belongs */
                    366:   BtCursor *pNext, *pPrev;  /* Forms a linked list of all cursors */
                    367:   BtCursor *pShared;        /* Loop of cursors with the same root page */
                    368:   Pgno pgnoRoot;            /* The root page of this tree */
                    369:   MemPage *pPage;           /* Page that contains the entry */
                    370:   int idx;                  /* Index of the entry in pPage->apCell[] */
                    371:   u8 wrFlag;                /* True if writable */
                    372:   u8 eSkip;                 /* Determines if next step operation is a no-op */
                    373:   u8 iMatch;                /* compare result from last sqliteBtreeMoveto() */
                    374: };
                    375: 
                    376: /*
                    377: ** Legal values for BtCursor.eSkip.
                    378: */
                    379: #define SKIP_NONE     0   /* Always step the cursor */
                    380: #define SKIP_NEXT     1   /* The next sqliteBtreeNext() is a no-op */
                    381: #define SKIP_PREV     2   /* The next sqliteBtreePrevious() is a no-op */
                    382: #define SKIP_INVALID  3   /* Calls to Next() and Previous() are invalid */
                    383: 
                    384: /* Forward declarations */
                    385: static int fileBtreeCloseCursor(BtCursor *pCur);
                    386: 
                    387: /*
                    388: ** Routines for byte swapping.
                    389: */
                    390: u16 swab16(u16 x){
                    391:   return ((x & 0xff)<<8) | ((x>>8)&0xff);
                    392: }
                    393: u32 swab32(u32 x){
                    394:   return ((x & 0xff)<<24) | ((x & 0xff00)<<8) |
                    395:          ((x>>8) & 0xff00) | ((x>>24)&0xff);
                    396: }
                    397: 
                    398: /*
                    399: ** Compute the total number of bytes that a Cell needs on the main
                    400: ** database page.  The number returned includes the Cell header,
                    401: ** local payload storage, and the pointer to overflow pages (if
                    402: ** applicable).  Additional space allocated on overflow pages
                    403: ** is NOT included in the value returned from this routine.
                    404: */
                    405: static int cellSize(Btree *pBt, Cell *pCell){
                    406:   int n = NKEY(pBt, pCell->h) + NDATA(pBt, pCell->h);
                    407:   if( n>MX_LOCAL_PAYLOAD ){
                    408:     n = MX_LOCAL_PAYLOAD + sizeof(Pgno);
                    409:   }else{
                    410:     n = ROUNDUP(n);
                    411:   }
                    412:   n += sizeof(CellHdr);
                    413:   return n;
                    414: }
                    415: 
                    416: /*
                    417: ** Defragment the page given.  All Cells are moved to the
                    418: ** beginning of the page and all free space is collected 
                    419: ** into one big FreeBlk at the end of the page.
                    420: */
                    421: static void defragmentPage(Btree *pBt, MemPage *pPage){
                    422:   int pc, i, n;
                    423:   FreeBlk *pFBlk;
                    424:   char newPage[SQLITE_USABLE_SIZE];
                    425: 
                    426:   assert( sqlitepager_iswriteable(pPage) );
                    427:   assert( pPage->isInit );
                    428:   pc = sizeof(PageHdr);
                    429:   pPage->u.hdr.firstCell = SWAB16(pBt, pc);
                    430:   memcpy(newPage, pPage->u.aDisk, pc);
                    431:   for(i=0; i<pPage->nCell; i++){
                    432:     Cell *pCell = pPage->apCell[i];
                    433: 
                    434:     /* This routine should never be called on an overfull page.  The
                    435:     ** following asserts verify that constraint. */
                    436:     assert( Addr(pCell) > Addr(pPage) );
                    437:     assert( Addr(pCell) < Addr(pPage) + SQLITE_USABLE_SIZE );
                    438: 
                    439:     n = cellSize(pBt, pCell);
                    440:     pCell->h.iNext = SWAB16(pBt, pc + n);
                    441:     memcpy(&newPage[pc], pCell, n);
                    442:     pPage->apCell[i] = (Cell*)&pPage->u.aDisk[pc];
                    443:     pc += n;
                    444:   }
                    445:   assert( pPage->nFree==SQLITE_USABLE_SIZE-pc );
                    446:   memcpy(pPage->u.aDisk, newPage, pc);
                    447:   if( pPage->nCell>0 ){
                    448:     pPage->apCell[pPage->nCell-1]->h.iNext = 0;
                    449:   }
                    450:   pFBlk = (FreeBlk*)&pPage->u.aDisk[pc];
                    451:   pFBlk->iSize = SWAB16(pBt, SQLITE_USABLE_SIZE - pc);
                    452:   pFBlk->iNext = 0;
                    453:   pPage->u.hdr.firstFree = SWAB16(pBt, pc);
                    454:   memset(&pFBlk[1], 0, SQLITE_USABLE_SIZE - pc - sizeof(FreeBlk));
                    455: }
                    456: 
                    457: /*
                    458: ** Allocate nByte bytes of space on a page.  nByte must be a 
                    459: ** multiple of 4.
                    460: **
                    461: ** Return the index into pPage->u.aDisk[] of the first byte of
                    462: ** the new allocation. Or return 0 if there is not enough free
                    463: ** space on the page to satisfy the allocation request.
                    464: **
                    465: ** If the page contains nBytes of free space but does not contain
                    466: ** nBytes of contiguous free space, then this routine automatically
                    467: ** calls defragementPage() to consolidate all free space before 
                    468: ** allocating the new chunk.
                    469: */
                    470: static int allocateSpace(Btree *pBt, MemPage *pPage, int nByte){
                    471:   FreeBlk *p;
                    472:   u16 *pIdx;
                    473:   int start;
                    474:   int iSize;
                    475: #ifndef NDEBUG
                    476:   int cnt = 0;
                    477: #endif
                    478: 
                    479:   assert( sqlitepager_iswriteable(pPage) );
                    480:   assert( nByte==ROUNDUP(nByte) );
                    481:   assert( pPage->isInit );
                    482:   if( pPage->nFree<nByte || pPage->isOverfull ) return 0;
                    483:   pIdx = &pPage->u.hdr.firstFree;
                    484:   p = (FreeBlk*)&pPage->u.aDisk[SWAB16(pBt, *pIdx)];
                    485:   while( (iSize = SWAB16(pBt, p->iSize))<nByte ){
                    486:     assert( cnt++ < SQLITE_USABLE_SIZE/4 );
                    487:     if( p->iNext==0 ){
                    488:       defragmentPage(pBt, pPage);
                    489:       pIdx = &pPage->u.hdr.firstFree;
                    490:     }else{
                    491:       pIdx = &p->iNext;
                    492:     }
                    493:     p = (FreeBlk*)&pPage->u.aDisk[SWAB16(pBt, *pIdx)];
                    494:   }
                    495:   if( iSize==nByte ){
                    496:     start = SWAB16(pBt, *pIdx);
                    497:     *pIdx = p->iNext;
                    498:   }else{
                    499:     FreeBlk *pNew;
                    500:     start = SWAB16(pBt, *pIdx);
                    501:     pNew = (FreeBlk*)&pPage->u.aDisk[start + nByte];
                    502:     pNew->iNext = p->iNext;
                    503:     pNew->iSize = SWAB16(pBt, iSize - nByte);
                    504:     *pIdx = SWAB16(pBt, start + nByte);
                    505:   }
                    506:   pPage->nFree -= nByte;
                    507:   return start;
                    508: }
                    509: 
                    510: /*
                    511: ** Return a section of the MemPage.u.aDisk[] to the freelist.
                    512: ** The first byte of the new free block is pPage->u.aDisk[start]
                    513: ** and the size of the block is "size" bytes.  Size must be
                    514: ** a multiple of 4.
                    515: **
                    516: ** Most of the effort here is involved in coalesing adjacent
                    517: ** free blocks into a single big free block.
                    518: */
                    519: static void freeSpace(Btree *pBt, MemPage *pPage, int start, int size){
                    520:   int end = start + size;
                    521:   u16 *pIdx, idx;
                    522:   FreeBlk *pFBlk;
                    523:   FreeBlk *pNew;
                    524:   FreeBlk *pNext;
                    525:   int iSize;
                    526: 
                    527:   assert( sqlitepager_iswriteable(pPage) );
                    528:   assert( size == ROUNDUP(size) );
                    529:   assert( start == ROUNDUP(start) );
                    530:   assert( pPage->isInit );
                    531:   pIdx = &pPage->u.hdr.firstFree;
                    532:   idx = SWAB16(pBt, *pIdx);
                    533:   while( idx!=0 && idx<start ){
                    534:     pFBlk = (FreeBlk*)&pPage->u.aDisk[idx];
                    535:     iSize = SWAB16(pBt, pFBlk->iSize);
                    536:     if( idx + iSize == start ){
                    537:       pFBlk->iSize = SWAB16(pBt, iSize + size);
                    538:       if( idx + iSize + size == SWAB16(pBt, pFBlk->iNext) ){
                    539:         pNext = (FreeBlk*)&pPage->u.aDisk[idx + iSize + size];
                    540:         if( pBt->needSwab ){
                    541:           pFBlk->iSize = swab16((u16)swab16(pNext->iSize)+iSize+size);
                    542:         }else{
                    543:           pFBlk->iSize += pNext->iSize;
                    544:         }
                    545:         pFBlk->iNext = pNext->iNext;
                    546:       }
                    547:       pPage->nFree += size;
                    548:       return;
                    549:     }
                    550:     pIdx = &pFBlk->iNext;
                    551:     idx = SWAB16(pBt, *pIdx);
                    552:   }
                    553:   pNew = (FreeBlk*)&pPage->u.aDisk[start];
                    554:   if( idx != end ){
                    555:     pNew->iSize = SWAB16(pBt, size);
                    556:     pNew->iNext = SWAB16(pBt, idx);
                    557:   }else{
                    558:     pNext = (FreeBlk*)&pPage->u.aDisk[idx];
                    559:     pNew->iSize = SWAB16(pBt, size + SWAB16(pBt, pNext->iSize));
                    560:     pNew->iNext = pNext->iNext;
                    561:   }
                    562:   *pIdx = SWAB16(pBt, start);
                    563:   pPage->nFree += size;
                    564: }
                    565: 
                    566: /*
                    567: ** Initialize the auxiliary information for a disk block.
                    568: **
                    569: ** The pParent parameter must be a pointer to the MemPage which
                    570: ** is the parent of the page being initialized.  The root of the
                    571: ** BTree (usually page 2) has no parent and so for that page, 
                    572: ** pParent==NULL.
                    573: **
                    574: ** Return SQLITE_OK on success.  If we see that the page does
                    575: ** not contain a well-formed database page, then return 
                    576: ** SQLITE_CORRUPT.  Note that a return of SQLITE_OK does not
                    577: ** guarantee that the page is well-formed.  It only shows that
                    578: ** we failed to detect any corruption.
                    579: */
                    580: static int initPage(Bt *pBt, MemPage *pPage, Pgno pgnoThis, MemPage *pParent){
                    581:   int idx;           /* An index into pPage->u.aDisk[] */
                    582:   Cell *pCell;       /* A pointer to a Cell in pPage->u.aDisk[] */
                    583:   FreeBlk *pFBlk;    /* A pointer to a free block in pPage->u.aDisk[] */
                    584:   int sz;            /* The size of a Cell in bytes */
                    585:   int freeSpace;     /* Amount of free space on the page */
                    586: 
                    587:   if( pPage->pParent ){
                    588:     assert( pPage->pParent==pParent );
                    589:     return SQLITE_OK;
                    590:   }
                    591:   if( pParent ){
                    592:     pPage->pParent = pParent;
                    593:     sqlitepager_ref(pParent);
                    594:   }
                    595:   if( pPage->isInit ) return SQLITE_OK;
                    596:   pPage->isInit = 1;
                    597:   pPage->nCell = 0;
                    598:   freeSpace = USABLE_SPACE;
                    599:   idx = SWAB16(pBt, pPage->u.hdr.firstCell);
                    600:   while( idx!=0 ){
                    601:     if( idx>SQLITE_USABLE_SIZE-MIN_CELL_SIZE ) goto page_format_error;
                    602:     if( idx<sizeof(PageHdr) ) goto page_format_error;
                    603:     if( idx!=ROUNDUP(idx) ) goto page_format_error;
                    604:     pCell = (Cell*)&pPage->u.aDisk[idx];
                    605:     sz = cellSize(pBt, pCell);
                    606:     if( idx+sz > SQLITE_USABLE_SIZE ) goto page_format_error;
                    607:     freeSpace -= sz;
                    608:     pPage->apCell[pPage->nCell++] = pCell;
                    609:     idx = SWAB16(pBt, pCell->h.iNext);
                    610:   }
                    611:   pPage->nFree = 0;
                    612:   idx = SWAB16(pBt, pPage->u.hdr.firstFree);
                    613:   while( idx!=0 ){
                    614:     int iNext;
                    615:     if( idx>SQLITE_USABLE_SIZE-sizeof(FreeBlk) ) goto page_format_error;
                    616:     if( idx<sizeof(PageHdr) ) goto page_format_error;
                    617:     pFBlk = (FreeBlk*)&pPage->u.aDisk[idx];
                    618:     pPage->nFree += SWAB16(pBt, pFBlk->iSize);
                    619:     iNext = SWAB16(pBt, pFBlk->iNext);
                    620:     if( iNext>0 && iNext <= idx ) goto page_format_error;
                    621:     idx = iNext;
                    622:   }
                    623:   if( pPage->nCell==0 && pPage->nFree==0 ){
                    624:     /* As a special case, an uninitialized root page appears to be
                    625:     ** an empty database */
                    626:     return SQLITE_OK;
                    627:   }
                    628:   if( pPage->nFree!=freeSpace ) goto page_format_error;
                    629:   return SQLITE_OK;
                    630: 
                    631: page_format_error:
                    632:   return SQLITE_CORRUPT;
                    633: }
                    634: 
                    635: /*
                    636: ** Set up a raw page so that it looks like a database page holding
                    637: ** no entries.
                    638: */
                    639: static void zeroPage(Btree *pBt, MemPage *pPage){
                    640:   PageHdr *pHdr;
                    641:   FreeBlk *pFBlk;
                    642:   assert( sqlitepager_iswriteable(pPage) );
                    643:   memset(pPage, 0, SQLITE_USABLE_SIZE);
                    644:   pHdr = &pPage->u.hdr;
                    645:   pHdr->firstCell = 0;
                    646:   pHdr->firstFree = SWAB16(pBt, sizeof(*pHdr));
                    647:   pFBlk = (FreeBlk*)&pHdr[1];
                    648:   pFBlk->iNext = 0;
                    649:   pPage->nFree = SQLITE_USABLE_SIZE - sizeof(*pHdr);
                    650:   pFBlk->iSize = SWAB16(pBt, pPage->nFree);
                    651:   pPage->nCell = 0;
                    652:   pPage->isOverfull = 0;
                    653: }
                    654: 
                    655: /*
                    656: ** This routine is called when the reference count for a page
                    657: ** reaches zero.  We need to unref the pParent pointer when that
                    658: ** happens.
                    659: */
                    660: static void pageDestructor(void *pData){
                    661:   MemPage *pPage = (MemPage*)pData;
                    662:   if( pPage->pParent ){
                    663:     MemPage *pParent = pPage->pParent;
                    664:     pPage->pParent = 0;
                    665:     sqlitepager_unref(pParent);
                    666:   }
                    667: }
                    668: 
                    669: /*
                    670: ** Open a new database.
                    671: **
                    672: ** Actually, this routine just sets up the internal data structures
                    673: ** for accessing the database.  We do not open the database file 
                    674: ** until the first page is loaded.
                    675: **
                    676: ** zFilename is the name of the database file.  If zFilename is NULL
                    677: ** a new database with a random name is created.  This randomly named
                    678: ** database file will be deleted when sqliteBtreeClose() is called.
                    679: */
                    680: int sqliteBtreeOpen(
                    681:   const char *zFilename,    /* Name of the file containing the BTree database */
                    682:   int omitJournal,          /* if TRUE then do not journal this file */
                    683:   int nCache,               /* How many pages in the page cache */
                    684:   Btree **ppBtree           /* Pointer to new Btree object written here */
                    685: ){
                    686:   Btree *pBt;
                    687:   int rc;
                    688: 
                    689:   /*
                    690:   ** The following asserts make sure that structures used by the btree are
                    691:   ** the right size.  This is to guard against size changes that result
                    692:   ** when compiling on a different architecture.
                    693:   */
                    694:   assert( sizeof(u32)==4 );
                    695:   assert( sizeof(u16)==2 );
                    696:   assert( sizeof(Pgno)==4 );
                    697:   assert( sizeof(PageHdr)==8 );
                    698:   assert( sizeof(CellHdr)==12 );
                    699:   assert( sizeof(FreeBlk)==4 );
                    700:   assert( sizeof(OverflowPage)==SQLITE_USABLE_SIZE );
                    701:   assert( sizeof(FreelistInfo)==OVERFLOW_SIZE );
                    702:   assert( sizeof(ptr)==sizeof(char*) );
                    703:   assert( sizeof(uptr)==sizeof(ptr) );
                    704: 
                    705:   pBt = sqliteMalloc( sizeof(*pBt) );
                    706:   if( pBt==0 ){
                    707:     *ppBtree = 0;
                    708:     return SQLITE_NOMEM;
                    709:   }
                    710:   if( nCache<10 ) nCache = 10;
                    711:   rc = sqlitepager_open(&pBt->pPager, zFilename, nCache, EXTRA_SIZE,
                    712:                         !omitJournal);
                    713:   if( rc!=SQLITE_OK ){
                    714:     if( pBt->pPager ) sqlitepager_close(pBt->pPager);
                    715:     sqliteFree(pBt);
                    716:     *ppBtree = 0;
                    717:     return rc;
                    718:   }
                    719:   sqlitepager_set_destructor(pBt->pPager, pageDestructor);
                    720:   pBt->pCursor = 0;
                    721:   pBt->page1 = 0;
                    722:   pBt->readOnly = sqlitepager_isreadonly(pBt->pPager);
                    723:   pBt->pOps = &sqliteBtreeOps;
                    724:   *ppBtree = pBt;
                    725:   return SQLITE_OK;
                    726: }
                    727: 
                    728: /*
                    729: ** Close an open database and invalidate all cursors.
                    730: */
                    731: static int fileBtreeClose(Btree *pBt){
                    732:   while( pBt->pCursor ){
                    733:     fileBtreeCloseCursor(pBt->pCursor);
                    734:   }
                    735:   sqlitepager_close(pBt->pPager);
                    736:   sqliteFree(pBt);
                    737:   return SQLITE_OK;
                    738: }
                    739: 
                    740: /*
                    741: ** Change the limit on the number of pages allowed in the cache.
                    742: **
                    743: ** The maximum number of cache pages is set to the absolute
                    744: ** value of mxPage.  If mxPage is negative, the pager will
                    745: ** operate asynchronously - it will not stop to do fsync()s
                    746: ** to insure data is written to the disk surface before
                    747: ** continuing.  Transactions still work if synchronous is off,
                    748: ** and the database cannot be corrupted if this program
                    749: ** crashes.  But if the operating system crashes or there is
                    750: ** an abrupt power failure when synchronous is off, the database
                    751: ** could be left in an inconsistent and unrecoverable state.
                    752: ** Synchronous is on by default so database corruption is not
                    753: ** normally a worry.
                    754: */
                    755: static int fileBtreeSetCacheSize(Btree *pBt, int mxPage){
                    756:   sqlitepager_set_cachesize(pBt->pPager, mxPage);
                    757:   return SQLITE_OK;
                    758: }
                    759: 
                    760: /*
                    761: ** Change the way data is synced to disk in order to increase or decrease
                    762: ** how well the database resists damage due to OS crashes and power
                    763: ** failures.  Level 1 is the same as asynchronous (no syncs() occur and
                    764: ** there is a high probability of damage)  Level 2 is the default.  There
                    765: ** is a very low but non-zero probability of damage.  Level 3 reduces the
                    766: ** probability of damage to near zero but with a write performance reduction.
                    767: */
                    768: static int fileBtreeSetSafetyLevel(Btree *pBt, int level){
                    769:   sqlitepager_set_safety_level(pBt->pPager, level);
                    770:   return SQLITE_OK;
                    771: }
                    772: 
                    773: /*
                    774: ** Get a reference to page1 of the database file.  This will
                    775: ** also acquire a readlock on that file.
                    776: **
                    777: ** SQLITE_OK is returned on success.  If the file is not a
                    778: ** well-formed database file, then SQLITE_CORRUPT is returned.
                    779: ** SQLITE_BUSY is returned if the database is locked.  SQLITE_NOMEM
                    780: ** is returned if we run out of memory.  SQLITE_PROTOCOL is returned
                    781: ** if there is a locking protocol violation.
                    782: */
                    783: static int lockBtree(Btree *pBt){
                    784:   int rc;
                    785:   if( pBt->page1 ) return SQLITE_OK;
                    786:   rc = sqlitepager_get(pBt->pPager, 1, (void**)&pBt->page1);
                    787:   if( rc!=SQLITE_OK ) return rc;
                    788: 
                    789:   /* Do some checking to help insure the file we opened really is
                    790:   ** a valid database file. 
                    791:   */
                    792:   if( sqlitepager_pagecount(pBt->pPager)>0 ){
                    793:     PageOne *pP1 = pBt->page1;
                    794:     if( strcmp(pP1->zMagic,zMagicHeader)!=0 ||
                    795:           (pP1->iMagic!=MAGIC && swab32(pP1->iMagic)!=MAGIC) ){
                    796:       rc = SQLITE_NOTADB;
                    797:       goto page1_init_failed;
                    798:     }
                    799:     pBt->needSwab = pP1->iMagic!=MAGIC;
                    800:   }
                    801:   return rc;
                    802: 
                    803: page1_init_failed:
                    804:   sqlitepager_unref(pBt->page1);
                    805:   pBt->page1 = 0;
                    806:   return rc;
                    807: }
                    808: 
                    809: /*
                    810: ** If there are no outstanding cursors and we are not in the middle
                    811: ** of a transaction but there is a read lock on the database, then
                    812: ** this routine unrefs the first page of the database file which 
                    813: ** has the effect of releasing the read lock.
                    814: **
                    815: ** If there are any outstanding cursors, this routine is a no-op.
                    816: **
                    817: ** If there is a transaction in progress, this routine is a no-op.
                    818: */
                    819: static void unlockBtreeIfUnused(Btree *pBt){
                    820:   if( pBt->inTrans==0 && pBt->pCursor==0 && pBt->page1!=0 ){
                    821:     sqlitepager_unref(pBt->page1);
                    822:     pBt->page1 = 0;
                    823:     pBt->inTrans = 0;
                    824:     pBt->inCkpt = 0;
                    825:   }
                    826: }
                    827: 
                    828: /*
                    829: ** Create a new database by initializing the first two pages of the
                    830: ** file.
                    831: */
                    832: static int newDatabase(Btree *pBt){
                    833:   MemPage *pRoot;
                    834:   PageOne *pP1;
                    835:   int rc;
                    836:   if( sqlitepager_pagecount(pBt->pPager)>1 ) return SQLITE_OK;
                    837:   pP1 = pBt->page1;
                    838:   rc = sqlitepager_write(pBt->page1);
                    839:   if( rc ) return rc;
                    840:   rc = sqlitepager_get(pBt->pPager, 2, (void**)&pRoot);
                    841:   if( rc ) return rc;
                    842:   rc = sqlitepager_write(pRoot);
                    843:   if( rc ){
                    844:     sqlitepager_unref(pRoot);
                    845:     return rc;
                    846:   }
                    847:   strcpy(pP1->zMagic, zMagicHeader);
                    848:   if( btree_native_byte_order ){
                    849:     pP1->iMagic = MAGIC;
                    850:     pBt->needSwab = 0;
                    851:   }else{
                    852:     pP1->iMagic = swab32(MAGIC);
                    853:     pBt->needSwab = 1;
                    854:   }
                    855:   zeroPage(pBt, pRoot);
                    856:   sqlitepager_unref(pRoot);
                    857:   return SQLITE_OK;
                    858: }
                    859: 
                    860: /*
                    861: ** Attempt to start a new transaction.
                    862: **
                    863: ** A transaction must be started before attempting any changes
                    864: ** to the database.  None of the following routines will work
                    865: ** unless a transaction is started first:
                    866: **
                    867: **      sqliteBtreeCreateTable()
                    868: **      sqliteBtreeCreateIndex()
                    869: **      sqliteBtreeClearTable()
                    870: **      sqliteBtreeDropTable()
                    871: **      sqliteBtreeInsert()
                    872: **      sqliteBtreeDelete()
                    873: **      sqliteBtreeUpdateMeta()
                    874: */
                    875: static int fileBtreeBeginTrans(Btree *pBt){
                    876:   int rc;
                    877:   if( pBt->inTrans ) return SQLITE_ERROR;
                    878:   if( pBt->readOnly ) return SQLITE_READONLY;
                    879:   if( pBt->page1==0 ){
                    880:     rc = lockBtree(pBt);
                    881:     if( rc!=SQLITE_OK ){
                    882:       return rc;
                    883:     }
                    884:   }
                    885:   rc = sqlitepager_begin(pBt->page1);
                    886:   if( rc==SQLITE_OK ){
                    887:     rc = newDatabase(pBt);
                    888:   }
                    889:   if( rc==SQLITE_OK ){
                    890:     pBt->inTrans = 1;
                    891:     pBt->inCkpt = 0;
                    892:   }else{
                    893:     unlockBtreeIfUnused(pBt);
                    894:   }
                    895:   return rc;
                    896: }
                    897: 
                    898: /*
                    899: ** Commit the transaction currently in progress.
                    900: **
                    901: ** This will release the write lock on the database file.  If there
                    902: ** are no active cursors, it also releases the read lock.
                    903: */
                    904: static int fileBtreeCommit(Btree *pBt){
                    905:   int rc;
                    906:   rc = pBt->readOnly ? SQLITE_OK : sqlitepager_commit(pBt->pPager);
                    907:   pBt->inTrans = 0;
                    908:   pBt->inCkpt = 0;
                    909:   unlockBtreeIfUnused(pBt);
                    910:   return rc;
                    911: }
                    912: 
                    913: /*
                    914: ** Rollback the transaction in progress.  All cursors will be
                    915: ** invalided by this operation.  Any attempt to use a cursor
                    916: ** that was open at the beginning of this operation will result
                    917: ** in an error.
                    918: **
                    919: ** This will release the write lock on the database file.  If there
                    920: ** are no active cursors, it also releases the read lock.
                    921: */
                    922: static int fileBtreeRollback(Btree *pBt){
                    923:   int rc;
                    924:   BtCursor *pCur;
                    925:   if( pBt->inTrans==0 ) return SQLITE_OK;
                    926:   pBt->inTrans = 0;
                    927:   pBt->inCkpt = 0;
                    928:   rc = pBt->readOnly ? SQLITE_OK : sqlitepager_rollback(pBt->pPager);
                    929:   for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
                    930:     if( pCur->pPage && pCur->pPage->isInit==0 ){
                    931:       sqlitepager_unref(pCur->pPage);
                    932:       pCur->pPage = 0;
                    933:     }
                    934:   }
                    935:   unlockBtreeIfUnused(pBt);
                    936:   return rc;
                    937: }
                    938: 
                    939: /*
                    940: ** Set the checkpoint for the current transaction.  The checkpoint serves
                    941: ** as a sub-transaction that can be rolled back independently of the
                    942: ** main transaction.  You must start a transaction before starting a
                    943: ** checkpoint.  The checkpoint is ended automatically if the transaction
                    944: ** commits or rolls back.
                    945: **
                    946: ** Only one checkpoint may be active at a time.  It is an error to try
                    947: ** to start a new checkpoint if another checkpoint is already active.
                    948: */
                    949: static int fileBtreeBeginCkpt(Btree *pBt){
                    950:   int rc;
                    951:   if( !pBt->inTrans || pBt->inCkpt ){
                    952:     return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
                    953:   }
                    954:   rc = pBt->readOnly ? SQLITE_OK : sqlitepager_ckpt_begin(pBt->pPager);
                    955:   pBt->inCkpt = 1;
                    956:   return rc;
                    957: }
                    958: 
                    959: 
                    960: /*
                    961: ** Commit a checkpoint to transaction currently in progress.  If no
                    962: ** checkpoint is active, this is a no-op.
                    963: */
                    964: static int fileBtreeCommitCkpt(Btree *pBt){
                    965:   int rc;
                    966:   if( pBt->inCkpt && !pBt->readOnly ){
                    967:     rc = sqlitepager_ckpt_commit(pBt->pPager);
                    968:   }else{
                    969:     rc = SQLITE_OK;
                    970:   }
                    971:   pBt->inCkpt = 0;
                    972:   return rc;
                    973: }
                    974: 
                    975: /*
                    976: ** Rollback the checkpoint to the current transaction.  If there
                    977: ** is no active checkpoint or transaction, this routine is a no-op.
                    978: **
                    979: ** All cursors will be invalided by this operation.  Any attempt
                    980: ** to use a cursor that was open at the beginning of this operation
                    981: ** will result in an error.
                    982: */
                    983: static int fileBtreeRollbackCkpt(Btree *pBt){
                    984:   int rc;
                    985:   BtCursor *pCur;
                    986:   if( pBt->inCkpt==0 || pBt->readOnly ) return SQLITE_OK;
                    987:   rc = sqlitepager_ckpt_rollback(pBt->pPager);
                    988:   for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
                    989:     if( pCur->pPage && pCur->pPage->isInit==0 ){
                    990:       sqlitepager_unref(pCur->pPage);
                    991:       pCur->pPage = 0;
                    992:     }
                    993:   }
                    994:   pBt->inCkpt = 0;
                    995:   return rc;
                    996: }
                    997: 
                    998: /*
                    999: ** Create a new cursor for the BTree whose root is on the page
                   1000: ** iTable.  The act of acquiring a cursor gets a read lock on 
                   1001: ** the database file.
                   1002: **
                   1003: ** If wrFlag==0, then the cursor can only be used for reading.
                   1004: ** If wrFlag==1, then the cursor can be used for reading or for
                   1005: ** writing if other conditions for writing are also met.  These
                   1006: ** are the conditions that must be met in order for writing to
                   1007: ** be allowed:
                   1008: **
                   1009: ** 1:  The cursor must have been opened with wrFlag==1
                   1010: **
                   1011: ** 2:  No other cursors may be open with wrFlag==0 on the same table
                   1012: **
                   1013: ** 3:  The database must be writable (not on read-only media)
                   1014: **
                   1015: ** 4:  There must be an active transaction.
                   1016: **
                   1017: ** Condition 2 warrants further discussion.  If any cursor is opened
                   1018: ** on a table with wrFlag==0, that prevents all other cursors from
                   1019: ** writing to that table.  This is a kind of "read-lock".  When a cursor
                   1020: ** is opened with wrFlag==0 it is guaranteed that the table will not
                   1021: ** change as long as the cursor is open.  This allows the cursor to
                   1022: ** do a sequential scan of the table without having to worry about
                   1023: ** entries being inserted or deleted during the scan.  Cursors should
                   1024: ** be opened with wrFlag==0 only if this read-lock property is needed.
                   1025: ** That is to say, cursors should be opened with wrFlag==0 only if they
                   1026: ** intend to use the sqliteBtreeNext() system call.  All other cursors
                   1027: ** should be opened with wrFlag==1 even if they never really intend
                   1028: ** to write.
                   1029: ** 
                   1030: ** No checking is done to make sure that page iTable really is the
                   1031: ** root page of a b-tree.  If it is not, then the cursor acquired
                   1032: ** will not work correctly.
                   1033: */
                   1034: static 
                   1035: int fileBtreeCursor(Btree *pBt, int iTable, int wrFlag, BtCursor **ppCur){
                   1036:   int rc;
                   1037:   BtCursor *pCur, *pRing;
                   1038: 
                   1039:   if( pBt->readOnly && wrFlag ){
                   1040:     *ppCur = 0;
                   1041:     return SQLITE_READONLY;
                   1042:   }
                   1043:   if( pBt->page1==0 ){
                   1044:     rc = lockBtree(pBt);
                   1045:     if( rc!=SQLITE_OK ){
                   1046:       *ppCur = 0;
                   1047:       return rc;
                   1048:     }
                   1049:   }
                   1050:   pCur = sqliteMalloc( sizeof(*pCur) );
                   1051:   if( pCur==0 ){
                   1052:     rc = SQLITE_NOMEM;
                   1053:     goto create_cursor_exception;
                   1054:   }
                   1055:   pCur->pgnoRoot = (Pgno)iTable;
                   1056:   rc = sqlitepager_get(pBt->pPager, pCur->pgnoRoot, (void**)&pCur->pPage);
                   1057:   if( rc!=SQLITE_OK ){
                   1058:     goto create_cursor_exception;
                   1059:   }
                   1060:   rc = initPage(pBt, pCur->pPage, pCur->pgnoRoot, 0);
                   1061:   if( rc!=SQLITE_OK ){
                   1062:     goto create_cursor_exception;
                   1063:   }
                   1064:   pCur->pOps = &sqliteBtreeCursorOps;
                   1065:   pCur->pBt = pBt;
                   1066:   pCur->wrFlag = wrFlag;
                   1067:   pCur->idx = 0;
                   1068:   pCur->eSkip = SKIP_INVALID;
                   1069:   pCur->pNext = pBt->pCursor;
                   1070:   if( pCur->pNext ){
                   1071:     pCur->pNext->pPrev = pCur;
                   1072:   }
                   1073:   pCur->pPrev = 0;
                   1074:   pRing = pBt->pCursor;
                   1075:   while( pRing && pRing->pgnoRoot!=pCur->pgnoRoot ){ pRing = pRing->pNext; }
                   1076:   if( pRing ){
                   1077:     pCur->pShared = pRing->pShared;
                   1078:     pRing->pShared = pCur;
                   1079:   }else{
                   1080:     pCur->pShared = pCur;
                   1081:   }
                   1082:   pBt->pCursor = pCur;
                   1083:   *ppCur = pCur;
                   1084:   return SQLITE_OK;
                   1085: 
                   1086: create_cursor_exception:
                   1087:   *ppCur = 0;
                   1088:   if( pCur ){
                   1089:     if( pCur->pPage ) sqlitepager_unref(pCur->pPage);
                   1090:     sqliteFree(pCur);
                   1091:   }
                   1092:   unlockBtreeIfUnused(pBt);
                   1093:   return rc;
                   1094: }
                   1095: 
                   1096: /*
                   1097: ** Close a cursor.  The read lock on the database file is released
                   1098: ** when the last cursor is closed.
                   1099: */
                   1100: static int fileBtreeCloseCursor(BtCursor *pCur){
                   1101:   Btree *pBt = pCur->pBt;
                   1102:   if( pCur->pPrev ){
                   1103:     pCur->pPrev->pNext = pCur->pNext;
                   1104:   }else{
                   1105:     pBt->pCursor = pCur->pNext;
                   1106:   }
                   1107:   if( pCur->pNext ){
                   1108:     pCur->pNext->pPrev = pCur->pPrev;
                   1109:   }
                   1110:   if( pCur->pPage ){
                   1111:     sqlitepager_unref(pCur->pPage);
                   1112:   }
                   1113:   if( pCur->pShared!=pCur ){
                   1114:     BtCursor *pRing = pCur->pShared;
                   1115:     while( pRing->pShared!=pCur ){ pRing = pRing->pShared; }
                   1116:     pRing->pShared = pCur->pShared;
                   1117:   }
                   1118:   unlockBtreeIfUnused(pBt);
                   1119:   sqliteFree(pCur);
                   1120:   return SQLITE_OK;
                   1121: }
                   1122: 
                   1123: /*
                   1124: ** Make a temporary cursor by filling in the fields of pTempCur.
                   1125: ** The temporary cursor is not on the cursor list for the Btree.
                   1126: */
                   1127: static void getTempCursor(BtCursor *pCur, BtCursor *pTempCur){
                   1128:   memcpy(pTempCur, pCur, sizeof(*pCur));
                   1129:   pTempCur->pNext = 0;
                   1130:   pTempCur->pPrev = 0;
                   1131:   if( pTempCur->pPage ){
                   1132:     sqlitepager_ref(pTempCur->pPage);
                   1133:   }
                   1134: }
                   1135: 
                   1136: /*
                   1137: ** Delete a temporary cursor such as was made by the CreateTemporaryCursor()
                   1138: ** function above.
                   1139: */
                   1140: static void releaseTempCursor(BtCursor *pCur){
                   1141:   if( pCur->pPage ){
                   1142:     sqlitepager_unref(pCur->pPage);
                   1143:   }
                   1144: }
                   1145: 
                   1146: /*
                   1147: ** Set *pSize to the number of bytes of key in the entry the
                   1148: ** cursor currently points to.  Always return SQLITE_OK.
                   1149: ** Failure is not possible.  If the cursor is not currently
                   1150: ** pointing to an entry (which can happen, for example, if
                   1151: ** the database is empty) then *pSize is set to 0.
                   1152: */
                   1153: static int fileBtreeKeySize(BtCursor *pCur, int *pSize){
                   1154:   Cell *pCell;
                   1155:   MemPage *pPage;
                   1156: 
                   1157:   pPage = pCur->pPage;
                   1158:   assert( pPage!=0 );
                   1159:   if( pCur->idx >= pPage->nCell ){
                   1160:     *pSize = 0;
                   1161:   }else{
                   1162:     pCell = pPage->apCell[pCur->idx];
                   1163:     *pSize = NKEY(pCur->pBt, pCell->h);
                   1164:   }
                   1165:   return SQLITE_OK;
                   1166: }
                   1167: 
                   1168: /*
                   1169: ** Read payload information from the entry that the pCur cursor is
                   1170: ** pointing to.  Begin reading the payload at "offset" and read
                   1171: ** a total of "amt" bytes.  Put the result in zBuf.
                   1172: **
                   1173: ** This routine does not make a distinction between key and data.
                   1174: ** It just reads bytes from the payload area.
                   1175: */
                   1176: static int getPayload(BtCursor *pCur, int offset, int amt, char *zBuf){
                   1177:   char *aPayload;
                   1178:   Pgno nextPage;
                   1179:   int rc;
                   1180:   Btree *pBt = pCur->pBt;
                   1181:   assert( pCur!=0 && pCur->pPage!=0 );
                   1182:   assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
                   1183:   aPayload = pCur->pPage->apCell[pCur->idx]->aPayload;
                   1184:   if( offset<MX_LOCAL_PAYLOAD ){
                   1185:     int a = amt;
                   1186:     if( a+offset>MX_LOCAL_PAYLOAD ){
                   1187:       a = MX_LOCAL_PAYLOAD - offset;
                   1188:     }
                   1189:     memcpy(zBuf, &aPayload[offset], a);
                   1190:     if( a==amt ){
                   1191:       return SQLITE_OK;
                   1192:     }
                   1193:     offset = 0;
                   1194:     zBuf += a;
                   1195:     amt -= a;
                   1196:   }else{
                   1197:     offset -= MX_LOCAL_PAYLOAD;
                   1198:   }
                   1199:   if( amt>0 ){
                   1200:     nextPage = SWAB32(pBt, pCur->pPage->apCell[pCur->idx]->ovfl);
                   1201:   }
                   1202:   while( amt>0 && nextPage ){
                   1203:     OverflowPage *pOvfl;
                   1204:     rc = sqlitepager_get(pBt->pPager, nextPage, (void**)&pOvfl);
                   1205:     if( rc!=0 ){
                   1206:       return rc;
                   1207:     }
                   1208:     nextPage = SWAB32(pBt, pOvfl->iNext);
                   1209:     if( offset<OVERFLOW_SIZE ){
                   1210:       int a = amt;
                   1211:       if( a + offset > OVERFLOW_SIZE ){
                   1212:         a = OVERFLOW_SIZE - offset;
                   1213:       }
                   1214:       memcpy(zBuf, &pOvfl->aPayload[offset], a);
                   1215:       offset = 0;
                   1216:       amt -= a;
                   1217:       zBuf += a;
                   1218:     }else{
                   1219:       offset -= OVERFLOW_SIZE;
                   1220:     }
                   1221:     sqlitepager_unref(pOvfl);
                   1222:   }
                   1223:   if( amt>0 ){
                   1224:     return SQLITE_CORRUPT;
                   1225:   }
                   1226:   return SQLITE_OK;
                   1227: }
                   1228: 
                   1229: /*
                   1230: ** Read part of the key associated with cursor pCur.  A maximum
                   1231: ** of "amt" bytes will be transfered into zBuf[].  The transfer
                   1232: ** begins at "offset".  The number of bytes actually read is
                   1233: ** returned. 
                   1234: **
                   1235: ** Change:  It used to be that the amount returned will be smaller
                   1236: ** than the amount requested if there are not enough bytes in the key
                   1237: ** to satisfy the request.  But now, it must be the case that there
                   1238: ** is enough data available to satisfy the request.  If not, an exception
                   1239: ** is raised.  The change was made in an effort to boost performance
                   1240: ** by eliminating unneeded tests.
                   1241: */
                   1242: static int fileBtreeKey(BtCursor *pCur, int offset, int amt, char *zBuf){
                   1243:   MemPage *pPage;
                   1244: 
                   1245:   assert( amt>=0 );
                   1246:   assert( offset>=0 );
                   1247:   assert( pCur->pPage!=0 );
                   1248:   pPage = pCur->pPage;
                   1249:   if( pCur->idx >= pPage->nCell ){
                   1250:     return 0;
                   1251:   }
                   1252:   assert( amt+offset <= NKEY(pCur->pBt, pPage->apCell[pCur->idx]->h) );
                   1253:   getPayload(pCur, offset, amt, zBuf);
                   1254:   return amt;
                   1255: }
                   1256: 
                   1257: /*
                   1258: ** Set *pSize to the number of bytes of data in the entry the
                   1259: ** cursor currently points to.  Always return SQLITE_OK.
                   1260: ** Failure is not possible.  If the cursor is not currently
                   1261: ** pointing to an entry (which can happen, for example, if
                   1262: ** the database is empty) then *pSize is set to 0.
                   1263: */
                   1264: static int fileBtreeDataSize(BtCursor *pCur, int *pSize){
                   1265:   Cell *pCell;
                   1266:   MemPage *pPage;
                   1267: 
                   1268:   pPage = pCur->pPage;
                   1269:   assert( pPage!=0 );
                   1270:   if( pCur->idx >= pPage->nCell ){
                   1271:     *pSize = 0;
                   1272:   }else{
                   1273:     pCell = pPage->apCell[pCur->idx];
                   1274:     *pSize = NDATA(pCur->pBt, pCell->h);
                   1275:   }
                   1276:   return SQLITE_OK;
                   1277: }
                   1278: 
                   1279: /*
                   1280: ** Read part of the data associated with cursor pCur.  A maximum
                   1281: ** of "amt" bytes will be transfered into zBuf[].  The transfer
                   1282: ** begins at "offset".  The number of bytes actually read is
                   1283: ** returned.  The amount returned will be smaller than the
                   1284: ** amount requested if there are not enough bytes in the data
                   1285: ** to satisfy the request.
                   1286: */
                   1287: static int fileBtreeData(BtCursor *pCur, int offset, int amt, char *zBuf){
                   1288:   Cell *pCell;
                   1289:   MemPage *pPage;
                   1290: 
                   1291:   assert( amt>=0 );
                   1292:   assert( offset>=0 );
                   1293:   assert( pCur->pPage!=0 );
                   1294:   pPage = pCur->pPage;
                   1295:   if( pCur->idx >= pPage->nCell ){
                   1296:     return 0;
                   1297:   }
                   1298:   pCell = pPage->apCell[pCur->idx];
                   1299:   assert( amt+offset <= NDATA(pCur->pBt, pCell->h) );
                   1300:   getPayload(pCur, offset + NKEY(pCur->pBt, pCell->h), amt, zBuf);
                   1301:   return amt;
                   1302: }
                   1303: 
                   1304: /*
                   1305: ** Compare an external key against the key on the entry that pCur points to.
                   1306: **
                   1307: ** The external key is pKey and is nKey bytes long.  The last nIgnore bytes
                   1308: ** of the key associated with pCur are ignored, as if they do not exist.
                   1309: ** (The normal case is for nIgnore to be zero in which case the entire
                   1310: ** internal key is used in the comparison.)
                   1311: **
                   1312: ** The comparison result is written to *pRes as follows:
                   1313: **
                   1314: **    *pRes<0    This means pCur<pKey
                   1315: **
                   1316: **    *pRes==0   This means pCur==pKey for all nKey bytes
                   1317: **
                   1318: **    *pRes>0    This means pCur>pKey
                   1319: **
                   1320: ** When one key is an exact prefix of the other, the shorter key is
                   1321: ** considered less than the longer one.  In order to be equal the
                   1322: ** keys must be exactly the same length. (The length of the pCur key
                   1323: ** is the actual key length minus nIgnore bytes.)
                   1324: */
                   1325: static int fileBtreeKeyCompare(
                   1326:   BtCursor *pCur,       /* Pointer to entry to compare against */
                   1327:   const void *pKey,     /* Key to compare against entry that pCur points to */
                   1328:   int nKey,             /* Number of bytes in pKey */
                   1329:   int nIgnore,          /* Ignore this many bytes at the end of pCur */
                   1330:   int *pResult          /* Write the result here */
                   1331: ){
                   1332:   Pgno nextPage;
                   1333:   int n, c, rc, nLocal;
                   1334:   Cell *pCell;
                   1335:   Btree *pBt = pCur->pBt;
                   1336:   const char *zKey  = (const char*)pKey;
                   1337: 
                   1338:   assert( pCur->pPage );
                   1339:   assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell );
                   1340:   pCell = pCur->pPage->apCell[pCur->idx];
                   1341:   nLocal = NKEY(pBt, pCell->h) - nIgnore;
                   1342:   if( nLocal<0 ) nLocal = 0;
                   1343:   n = nKey<nLocal ? nKey : nLocal;
                   1344:   if( n>MX_LOCAL_PAYLOAD ){
                   1345:     n = MX_LOCAL_PAYLOAD;
                   1346:   }
                   1347:   c = memcmp(pCell->aPayload, zKey, n);
                   1348:   if( c!=0 ){
                   1349:     *pResult = c;
                   1350:     return SQLITE_OK;
                   1351:   }
                   1352:   zKey += n;
                   1353:   nKey -= n;
                   1354:   nLocal -= n;
                   1355:   nextPage = SWAB32(pBt, pCell->ovfl);
                   1356:   while( nKey>0 && nLocal>0 ){
                   1357:     OverflowPage *pOvfl;
                   1358:     if( nextPage==0 ){
                   1359:       return SQLITE_CORRUPT;
                   1360:     }
                   1361:     rc = sqlitepager_get(pBt->pPager, nextPage, (void**)&pOvfl);
                   1362:     if( rc ){
                   1363:       return rc;
                   1364:     }
                   1365:     nextPage = SWAB32(pBt, pOvfl->iNext);
                   1366:     n = nKey<nLocal ? nKey : nLocal;
                   1367:     if( n>OVERFLOW_SIZE ){
                   1368:       n = OVERFLOW_SIZE;
                   1369:     }
                   1370:     c = memcmp(pOvfl->aPayload, zKey, n);
                   1371:     sqlitepager_unref(pOvfl);
                   1372:     if( c!=0 ){
                   1373:       *pResult = c;
                   1374:       return SQLITE_OK;
                   1375:     }
                   1376:     nKey -= n;
                   1377:     nLocal -= n;
                   1378:     zKey += n;
                   1379:   }
                   1380:   if( c==0 ){
                   1381:     c = nLocal - nKey;
                   1382:   }
                   1383:   *pResult = c;
                   1384:   return SQLITE_OK;
                   1385: }
                   1386: 
                   1387: /*
                   1388: ** Move the cursor down to a new child page.  The newPgno argument is the
                   1389: ** page number of the child page in the byte order of the disk image.
                   1390: */
                   1391: static int moveToChild(BtCursor *pCur, int newPgno){
                   1392:   int rc;
                   1393:   MemPage *pNewPage;
                   1394:   Btree *pBt = pCur->pBt;
                   1395: 
                   1396:   newPgno = SWAB32(pBt, newPgno);
                   1397:   rc = sqlitepager_get(pBt->pPager, newPgno, (void**)&pNewPage);
                   1398:   if( rc ) return rc;
                   1399:   rc = initPage(pBt, pNewPage, newPgno, pCur->pPage);
                   1400:   if( rc ) return rc;
                   1401:   assert( pCur->idx>=pCur->pPage->nCell
                   1402:           || pCur->pPage->apCell[pCur->idx]->h.leftChild==SWAB32(pBt,newPgno) );
                   1403:   assert( pCur->idx<pCur->pPage->nCell
                   1404:           || pCur->pPage->u.hdr.rightChild==SWAB32(pBt,newPgno) );
                   1405:   pNewPage->idxParent = pCur->idx;
                   1406:   pCur->pPage->idxShift = 0;
                   1407:   sqlitepager_unref(pCur->pPage);
                   1408:   pCur->pPage = pNewPage;
                   1409:   pCur->idx = 0;
                   1410:   if( pNewPage->nCell<1 ){
                   1411:     return SQLITE_CORRUPT;
                   1412:   }
                   1413:   return SQLITE_OK;
                   1414: }
                   1415: 
                   1416: /*
                   1417: ** Move the cursor up to the parent page.
                   1418: **
                   1419: ** pCur->idx is set to the cell index that contains the pointer
                   1420: ** to the page we are coming from.  If we are coming from the
                   1421: ** right-most child page then pCur->idx is set to one more than
                   1422: ** the largest cell index.
                   1423: */
                   1424: static void moveToParent(BtCursor *pCur){
                   1425:   Pgno oldPgno;
                   1426:   MemPage *pParent;
                   1427:   MemPage *pPage;
                   1428:   int idxParent;
                   1429:   pPage = pCur->pPage;
                   1430:   assert( pPage!=0 );
                   1431:   pParent = pPage->pParent;
                   1432:   assert( pParent!=0 );
                   1433:   idxParent = pPage->idxParent;
                   1434:   sqlitepager_ref(pParent);
                   1435:   sqlitepager_unref(pPage);
                   1436:   pCur->pPage = pParent;
                   1437:   assert( pParent->idxShift==0 );
                   1438:   if( pParent->idxShift==0 ){
                   1439:     pCur->idx = idxParent;
                   1440: #ifndef NDEBUG  
                   1441:     /* Verify that pCur->idx is the correct index to point back to the child
                   1442:     ** page we just came from 
                   1443:     */
                   1444:     oldPgno = SWAB32(pCur->pBt, sqlitepager_pagenumber(pPage));
                   1445:     if( pCur->idx<pParent->nCell ){
                   1446:       assert( pParent->apCell[idxParent]->h.leftChild==oldPgno );
                   1447:     }else{
                   1448:       assert( pParent->u.hdr.rightChild==oldPgno );
                   1449:     }
                   1450: #endif
                   1451:   }else{
                   1452:     /* The MemPage.idxShift flag indicates that cell indices might have 
                   1453:     ** changed since idxParent was set and hence idxParent might be out
                   1454:     ** of date.  So recompute the parent cell index by scanning all cells
                   1455:     ** and locating the one that points to the child we just came from.
                   1456:     */
                   1457:     int i;
                   1458:     pCur->idx = pParent->nCell;
                   1459:     oldPgno = SWAB32(pCur->pBt, sqlitepager_pagenumber(pPage));
                   1460:     for(i=0; i<pParent->nCell; i++){
                   1461:       if( pParent->apCell[i]->h.leftChild==oldPgno ){
                   1462:         pCur->idx = i;
                   1463:         break;
                   1464:       }
                   1465:     }
                   1466:   }
                   1467: }
                   1468: 
                   1469: /*
                   1470: ** Move the cursor to the root page
                   1471: */
                   1472: static int moveToRoot(BtCursor *pCur){
                   1473:   MemPage *pNew;
                   1474:   int rc;
                   1475:   Btree *pBt = pCur->pBt;
                   1476: 
                   1477:   rc = sqlitepager_get(pBt->pPager, pCur->pgnoRoot, (void**)&pNew);
                   1478:   if( rc ) return rc;
                   1479:   rc = initPage(pBt, pNew, pCur->pgnoRoot, 0);
                   1480:   if( rc ) return rc;
                   1481:   sqlitepager_unref(pCur->pPage);
                   1482:   pCur->pPage = pNew;
                   1483:   pCur->idx = 0;
                   1484:   return SQLITE_OK;
                   1485: }
                   1486: 
                   1487: /*
                   1488: ** Move the cursor down to the left-most leaf entry beneath the
                   1489: ** entry to which it is currently pointing.
                   1490: */
                   1491: static int moveToLeftmost(BtCursor *pCur){
                   1492:   Pgno pgno;
                   1493:   int rc;
                   1494: 
                   1495:   while( (pgno = pCur->pPage->apCell[pCur->idx]->h.leftChild)!=0 ){
                   1496:     rc = moveToChild(pCur, pgno);
                   1497:     if( rc ) return rc;
                   1498:   }
                   1499:   return SQLITE_OK;
                   1500: }
                   1501: 
                   1502: /*
                   1503: ** Move the cursor down to the right-most leaf entry beneath the
                   1504: ** page to which it is currently pointing.  Notice the difference
                   1505: ** between moveToLeftmost() and moveToRightmost().  moveToLeftmost()
                   1506: ** finds the left-most entry beneath the *entry* whereas moveToRightmost()
                   1507: ** finds the right-most entry beneath the *page*.
                   1508: */
                   1509: static int moveToRightmost(BtCursor *pCur){
                   1510:   Pgno pgno;
                   1511:   int rc;
                   1512: 
                   1513:   while( (pgno = pCur->pPage->u.hdr.rightChild)!=0 ){
                   1514:     pCur->idx = pCur->pPage->nCell;
                   1515:     rc = moveToChild(pCur, pgno);
                   1516:     if( rc ) return rc;
                   1517:   }
                   1518:   pCur->idx = pCur->pPage->nCell - 1;
                   1519:   return SQLITE_OK;
                   1520: }
                   1521: 
                   1522: /* Move the cursor to the first entry in the table.  Return SQLITE_OK
                   1523: ** on success.  Set *pRes to 0 if the cursor actually points to something
                   1524: ** or set *pRes to 1 if the table is empty.
                   1525: */
                   1526: static int fileBtreeFirst(BtCursor *pCur, int *pRes){
                   1527:   int rc;
                   1528:   if( pCur->pPage==0 ) return SQLITE_ABORT;
                   1529:   rc = moveToRoot(pCur);
                   1530:   if( rc ) return rc;
                   1531:   if( pCur->pPage->nCell==0 ){
                   1532:     *pRes = 1;
                   1533:     return SQLITE_OK;
                   1534:   }
                   1535:   *pRes = 0;
                   1536:   rc = moveToLeftmost(pCur);
                   1537:   pCur->eSkip = SKIP_NONE;
                   1538:   return rc;
                   1539: }
                   1540: 
                   1541: /* Move the cursor to the last entry in the table.  Return SQLITE_OK
                   1542: ** on success.  Set *pRes to 0 if the cursor actually points to something
                   1543: ** or set *pRes to 1 if the table is empty.
                   1544: */
                   1545: static int fileBtreeLast(BtCursor *pCur, int *pRes){
                   1546:   int rc;
                   1547:   if( pCur->pPage==0 ) return SQLITE_ABORT;
                   1548:   rc = moveToRoot(pCur);
                   1549:   if( rc ) return rc;
                   1550:   assert( pCur->pPage->isInit );
                   1551:   if( pCur->pPage->nCell==0 ){
                   1552:     *pRes = 1;
                   1553:     return SQLITE_OK;
                   1554:   }
                   1555:   *pRes = 0;
                   1556:   rc = moveToRightmost(pCur);
                   1557:   pCur->eSkip = SKIP_NONE;
                   1558:   return rc;
                   1559: }
                   1560: 
                   1561: /* Move the cursor so that it points to an entry near pKey.
                   1562: ** Return a success code.
                   1563: **
                   1564: ** If an exact match is not found, then the cursor is always
                   1565: ** left pointing at a leaf page which would hold the entry if it
                   1566: ** were present.  The cursor might point to an entry that comes
                   1567: ** before or after the key.
                   1568: **
                   1569: ** The result of comparing the key with the entry to which the
                   1570: ** cursor is left pointing is stored in pCur->iMatch.  The same
                   1571: ** value is also written to *pRes if pRes!=NULL.  The meaning of
                   1572: ** this value is as follows:
                   1573: **
                   1574: **     *pRes<0      The cursor is left pointing at an entry that
                   1575: **                  is smaller than pKey or if the table is empty
                   1576: **                  and the cursor is therefore left point to nothing.
                   1577: **
                   1578: **     *pRes==0     The cursor is left pointing at an entry that
                   1579: **                  exactly matches pKey.
                   1580: **
                   1581: **     *pRes>0      The cursor is left pointing at an entry that
                   1582: **                  is larger than pKey.
                   1583: */
                   1584: static
                   1585: int fileBtreeMoveto(BtCursor *pCur, const void *pKey, int nKey, int *pRes){
                   1586:   int rc;
                   1587:   if( pCur->pPage==0 ) return SQLITE_ABORT;
                   1588:   pCur->eSkip = SKIP_NONE;
                   1589:   rc = moveToRoot(pCur);
                   1590:   if( rc ) return rc;
                   1591:   for(;;){
                   1592:     int lwr, upr;
                   1593:     Pgno chldPg;
                   1594:     MemPage *pPage = pCur->pPage;
                   1595:     int c = -1;  /* pRes return if table is empty must be -1 */
                   1596:     lwr = 0;
                   1597:     upr = pPage->nCell-1;
                   1598:     while( lwr<=upr ){
                   1599:       pCur->idx = (lwr+upr)/2;
                   1600:       rc = fileBtreeKeyCompare(pCur, pKey, nKey, 0, &c);
                   1601:       if( rc ) return rc;
                   1602:       if( c==0 ){
                   1603:         pCur->iMatch = c;
                   1604:         if( pRes ) *pRes = 0;
                   1605:         return SQLITE_OK;
                   1606:       }
                   1607:       if( c<0 ){
                   1608:         lwr = pCur->idx+1;
                   1609:       }else{
                   1610:         upr = pCur->idx-1;
                   1611:       }
                   1612:     }
                   1613:     assert( lwr==upr+1 );
                   1614:     assert( pPage->isInit );
                   1615:     if( lwr>=pPage->nCell ){
                   1616:       chldPg = pPage->u.hdr.rightChild;
                   1617:     }else{
                   1618:       chldPg = pPage->apCell[lwr]->h.leftChild;
                   1619:     }
                   1620:     if( chldPg==0 ){
                   1621:       pCur->iMatch = c;
                   1622:       if( pRes ) *pRes = c;
                   1623:       return SQLITE_OK;
                   1624:     }
                   1625:     pCur->idx = lwr;
                   1626:     rc = moveToChild(pCur, chldPg);
                   1627:     if( rc ) return rc;
                   1628:   }
                   1629:   /* NOT REACHED */
                   1630: }
                   1631: 
                   1632: /*
                   1633: ** Advance the cursor to the next entry in the database.  If
                   1634: ** successful then set *pRes=0.  If the cursor
                   1635: ** was already pointing to the last entry in the database before
                   1636: ** this routine was called, then set *pRes=1.
                   1637: */
                   1638: static int fileBtreeNext(BtCursor *pCur, int *pRes){
                   1639:   int rc;
                   1640:   MemPage *pPage = pCur->pPage;
                   1641:   assert( pRes!=0 );
                   1642:   if( pPage==0 ){
                   1643:     *pRes = 1;
                   1644:     return SQLITE_ABORT;
                   1645:   }
                   1646:   assert( pPage->isInit );
                   1647:   assert( pCur->eSkip!=SKIP_INVALID );
                   1648:   if( pPage->nCell==0 ){
                   1649:     *pRes = 1;
                   1650:     return SQLITE_OK;
                   1651:   }
                   1652:   assert( pCur->idx<pPage->nCell );
                   1653:   if( pCur->eSkip==SKIP_NEXT ){
                   1654:     pCur->eSkip = SKIP_NONE;
                   1655:     *pRes = 0;
                   1656:     return SQLITE_OK;
                   1657:   }
                   1658:   pCur->eSkip = SKIP_NONE;
                   1659:   pCur->idx++;
                   1660:   if( pCur->idx>=pPage->nCell ){
                   1661:     if( pPage->u.hdr.rightChild ){
                   1662:       rc = moveToChild(pCur, pPage->u.hdr.rightChild);
                   1663:       if( rc ) return rc;
                   1664:       rc = moveToLeftmost(pCur);
                   1665:       *pRes = 0;
                   1666:       return rc;
                   1667:     }
                   1668:     do{
                   1669:       if( pPage->pParent==0 ){
                   1670:         *pRes = 1;
                   1671:         return SQLITE_OK;
                   1672:       }
                   1673:       moveToParent(pCur);
                   1674:       pPage = pCur->pPage;
                   1675:     }while( pCur->idx>=pPage->nCell );
                   1676:     *pRes = 0;
                   1677:     return SQLITE_OK;
                   1678:   }
                   1679:   *pRes = 0;
                   1680:   if( pPage->u.hdr.rightChild==0 ){
                   1681:     return SQLITE_OK;
                   1682:   }
                   1683:   rc = moveToLeftmost(pCur);
                   1684:   return rc;
                   1685: }
                   1686: 
                   1687: /*
                   1688: ** Step the cursor to the back to the previous entry in the database.  If
                   1689: ** successful then set *pRes=0.  If the cursor
                   1690: ** was already pointing to the first entry in the database before
                   1691: ** this routine was called, then set *pRes=1.
                   1692: */
                   1693: static int fileBtreePrevious(BtCursor *pCur, int *pRes){
                   1694:   int rc;
                   1695:   Pgno pgno;
                   1696:   MemPage *pPage;
                   1697:   pPage = pCur->pPage;
                   1698:   if( pPage==0 ){
                   1699:     *pRes = 1;
                   1700:     return SQLITE_ABORT;
                   1701:   }
                   1702:   assert( pPage->isInit );
                   1703:   assert( pCur->eSkip!=SKIP_INVALID );
                   1704:   if( pPage->nCell==0 ){
                   1705:     *pRes = 1;
                   1706:     return SQLITE_OK;
                   1707:   }
                   1708:   if( pCur->eSkip==SKIP_PREV ){
                   1709:     pCur->eSkip = SKIP_NONE;
                   1710:     *pRes = 0;
                   1711:     return SQLITE_OK;
                   1712:   }
                   1713:   pCur->eSkip = SKIP_NONE;
                   1714:   assert( pCur->idx>=0 );
                   1715:   if( (pgno = pPage->apCell[pCur->idx]->h.leftChild)!=0 ){
                   1716:     rc = moveToChild(pCur, pgno);
                   1717:     if( rc ) return rc;
                   1718:     rc = moveToRightmost(pCur);
                   1719:   }else{
                   1720:     while( pCur->idx==0 ){
                   1721:       if( pPage->pParent==0 ){
                   1722:         if( pRes ) *pRes = 1;
                   1723:         return SQLITE_OK;
                   1724:       }
                   1725:       moveToParent(pCur);
                   1726:       pPage = pCur->pPage;
                   1727:     }
                   1728:     pCur->idx--;
                   1729:     rc = SQLITE_OK;
                   1730:   }
                   1731:   *pRes = 0;
                   1732:   return rc;
                   1733: }
                   1734: 
                   1735: /*
                   1736: ** Allocate a new page from the database file.
                   1737: **
                   1738: ** The new page is marked as dirty.  (In other words, sqlitepager_write()
                   1739: ** has already been called on the new page.)  The new page has also
                   1740: ** been referenced and the calling routine is responsible for calling
                   1741: ** sqlitepager_unref() on the new page when it is done.
                   1742: **
                   1743: ** SQLITE_OK is returned on success.  Any other return value indicates
                   1744: ** an error.  *ppPage and *pPgno are undefined in the event of an error.
                   1745: ** Do not invoke sqlitepager_unref() on *ppPage if an error is returned.
                   1746: **
                   1747: ** If the "nearby" parameter is not 0, then a (feeble) effort is made to 
                   1748: ** locate a page close to the page number "nearby".  This can be used in an
                   1749: ** attempt to keep related pages close to each other in the database file,
                   1750: ** which in turn can make database access faster.
                   1751: */
                   1752: static int allocatePage(Btree *pBt, MemPage **ppPage, Pgno *pPgno, Pgno nearby){
                   1753:   PageOne *pPage1 = pBt->page1;
                   1754:   int rc;
                   1755:   if( pPage1->freeList ){
                   1756:     OverflowPage *pOvfl;
                   1757:     FreelistInfo *pInfo;
                   1758: 
                   1759:     rc = sqlitepager_write(pPage1);
                   1760:     if( rc ) return rc;
                   1761:     SWAB_ADD(pBt, pPage1->nFree, -1);
                   1762:     rc = sqlitepager_get(pBt->pPager, SWAB32(pBt, pPage1->freeList),
                   1763:                         (void**)&pOvfl);
                   1764:     if( rc ) return rc;
                   1765:     rc = sqlitepager_write(pOvfl);
                   1766:     if( rc ){
                   1767:       sqlitepager_unref(pOvfl);
                   1768:       return rc;
                   1769:     }
                   1770:     pInfo = (FreelistInfo*)pOvfl->aPayload;
                   1771:     if( pInfo->nFree==0 ){
                   1772:       *pPgno = SWAB32(pBt, pPage1->freeList);
                   1773:       pPage1->freeList = pOvfl->iNext;
                   1774:       *ppPage = (MemPage*)pOvfl;
                   1775:     }else{
                   1776:       int closest, n;
                   1777:       n = SWAB32(pBt, pInfo->nFree);
                   1778:       if( n>1 && nearby>0 ){
                   1779:         int i, dist;
                   1780:         closest = 0;
                   1781:         dist = SWAB32(pBt, pInfo->aFree[0]) - nearby;
                   1782:         if( dist<0 ) dist = -dist;
                   1783:         for(i=1; i<n; i++){
                   1784:           int d2 = SWAB32(pBt, pInfo->aFree[i]) - nearby;
                   1785:           if( d2<0 ) d2 = -d2;
                   1786:           if( d2<dist ) closest = i;
                   1787:         }
                   1788:       }else{
                   1789:         closest = 0;
                   1790:       }
                   1791:       SWAB_ADD(pBt, pInfo->nFree, -1);
                   1792:       *pPgno = SWAB32(pBt, pInfo->aFree[closest]);
                   1793:       pInfo->aFree[closest] = pInfo->aFree[n-1];
                   1794:       rc = sqlitepager_get(pBt->pPager, *pPgno, (void**)ppPage);
                   1795:       sqlitepager_unref(pOvfl);
                   1796:       if( rc==SQLITE_OK ){
                   1797:         sqlitepager_dont_rollback(*ppPage);
                   1798:         rc = sqlitepager_write(*ppPage);
                   1799:       }
                   1800:     }
                   1801:   }else{
                   1802:     *pPgno = sqlitepager_pagecount(pBt->pPager) + 1;
                   1803:     rc = sqlitepager_get(pBt->pPager, *pPgno, (void**)ppPage);
                   1804:     if( rc ) return rc;
                   1805:     rc = sqlitepager_write(*ppPage);
                   1806:   }
                   1807:   return rc;
                   1808: }
                   1809: 
                   1810: /*
                   1811: ** Add a page of the database file to the freelist.  Either pgno or
                   1812: ** pPage but not both may be 0. 
                   1813: **
                   1814: ** sqlitepager_unref() is NOT called for pPage.
                   1815: */
                   1816: static int freePage(Btree *pBt, void *pPage, Pgno pgno){
                   1817:   PageOne *pPage1 = pBt->page1;
                   1818:   OverflowPage *pOvfl = (OverflowPage*)pPage;
                   1819:   int rc;
                   1820:   int needUnref = 0;
                   1821:   MemPage *pMemPage;
                   1822: 
                   1823:   if( pgno==0 ){
                   1824:     assert( pOvfl!=0 );
                   1825:     pgno = sqlitepager_pagenumber(pOvfl);
                   1826:   }
                   1827:   assert( pgno>2 );
                   1828:   assert( sqlitepager_pagenumber(pOvfl)==pgno );
                   1829:   pMemPage = (MemPage*)pPage;
                   1830:   pMemPage->isInit = 0;
                   1831:   if( pMemPage->pParent ){
                   1832:     sqlitepager_unref(pMemPage->pParent);
                   1833:     pMemPage->pParent = 0;
                   1834:   }
                   1835:   rc = sqlitepager_write(pPage1);
                   1836:   if( rc ){
                   1837:     return rc;
                   1838:   }
                   1839:   SWAB_ADD(pBt, pPage1->nFree, 1);
                   1840:   if( pPage1->nFree!=0 && pPage1->freeList!=0 ){
                   1841:     OverflowPage *pFreeIdx;
                   1842:     rc = sqlitepager_get(pBt->pPager, SWAB32(pBt, pPage1->freeList),
                   1843:                         (void**)&pFreeIdx);
                   1844:     if( rc==SQLITE_OK ){
                   1845:       FreelistInfo *pInfo = (FreelistInfo*)pFreeIdx->aPayload;
                   1846:       int n = SWAB32(pBt, pInfo->nFree);
                   1847:       if( n<(sizeof(pInfo->aFree)/sizeof(pInfo->aFree[0])) ){
                   1848:         rc = sqlitepager_write(pFreeIdx);
                   1849:         if( rc==SQLITE_OK ){
                   1850:           pInfo->aFree[n] = SWAB32(pBt, pgno);
                   1851:           SWAB_ADD(pBt, pInfo->nFree, 1);
                   1852:           sqlitepager_unref(pFreeIdx);
                   1853:           sqlitepager_dont_write(pBt->pPager, pgno);
                   1854:           return rc;
                   1855:         }
                   1856:       }
                   1857:       sqlitepager_unref(pFreeIdx);
                   1858:     }
                   1859:   }
                   1860:   if( pOvfl==0 ){
                   1861:     assert( pgno>0 );
                   1862:     rc = sqlitepager_get(pBt->pPager, pgno, (void**)&pOvfl);
                   1863:     if( rc ) return rc;
                   1864:     needUnref = 1;
                   1865:   }
                   1866:   rc = sqlitepager_write(pOvfl);
                   1867:   if( rc ){
                   1868:     if( needUnref ) sqlitepager_unref(pOvfl);
                   1869:     return rc;
                   1870:   }
                   1871:   pOvfl->iNext = pPage1->freeList;
                   1872:   pPage1->freeList = SWAB32(pBt, pgno);
                   1873:   memset(pOvfl->aPayload, 0, OVERFLOW_SIZE);
                   1874:   if( needUnref ) rc = sqlitepager_unref(pOvfl);
                   1875:   return rc;
                   1876: }
                   1877: 
                   1878: /*
                   1879: ** Erase all the data out of a cell.  This involves returning overflow
                   1880: ** pages back the freelist.
                   1881: */
                   1882: static int clearCell(Btree *pBt, Cell *pCell){
                   1883:   Pager *pPager = pBt->pPager;
                   1884:   OverflowPage *pOvfl;
                   1885:   Pgno ovfl, nextOvfl;
                   1886:   int rc;
                   1887: 
                   1888:   if( NKEY(pBt, pCell->h) + NDATA(pBt, pCell->h) <= MX_LOCAL_PAYLOAD ){
                   1889:     return SQLITE_OK;
                   1890:   }
                   1891:   ovfl = SWAB32(pBt, pCell->ovfl);
                   1892:   pCell->ovfl = 0;
                   1893:   while( ovfl ){
                   1894:     rc = sqlitepager_get(pPager, ovfl, (void**)&pOvfl);
                   1895:     if( rc ) return rc;
                   1896:     nextOvfl = SWAB32(pBt, pOvfl->iNext);
                   1897:     rc = freePage(pBt, pOvfl, ovfl);
                   1898:     if( rc ) return rc;
                   1899:     sqlitepager_unref(pOvfl);
                   1900:     ovfl = nextOvfl;
                   1901:   }
                   1902:   return SQLITE_OK;
                   1903: }
                   1904: 
                   1905: /*
                   1906: ** Create a new cell from key and data.  Overflow pages are allocated as
                   1907: ** necessary and linked to this cell.  
                   1908: */
                   1909: static int fillInCell(
                   1910:   Btree *pBt,              /* The whole Btree.  Needed to allocate pages */
                   1911:   Cell *pCell,             /* Populate this Cell structure */
                   1912:   const void *pKey, int nKey,    /* The key */
                   1913:   const void *pData,int nData    /* The data */
                   1914: ){
                   1915:   OverflowPage *pOvfl, *pPrior;
                   1916:   Pgno *pNext;
                   1917:   int spaceLeft;
                   1918:   int n, rc;
                   1919:   int nPayload;
                   1920:   const char *pPayload;
                   1921:   char *pSpace;
                   1922:   Pgno nearby = 0;
                   1923: 
                   1924:   pCell->h.leftChild = 0;
                   1925:   pCell->h.nKey = SWAB16(pBt, nKey & 0xffff);
                   1926:   pCell->h.nKeyHi = nKey >> 16;
                   1927:   pCell->h.nData = SWAB16(pBt, nData & 0xffff);
                   1928:   pCell->h.nDataHi = nData >> 16;
                   1929:   pCell->h.iNext = 0;
                   1930: 
                   1931:   pNext = &pCell->ovfl;
                   1932:   pSpace = pCell->aPayload;
                   1933:   spaceLeft = MX_LOCAL_PAYLOAD;
                   1934:   pPayload = pKey;
                   1935:   pKey = 0;
                   1936:   nPayload = nKey;
                   1937:   pPrior = 0;
                   1938:   while( nPayload>0 ){
                   1939:     if( spaceLeft==0 ){
                   1940:       rc = allocatePage(pBt, (MemPage**)&pOvfl, pNext, nearby);
                   1941:       if( rc ){
                   1942:         *pNext = 0;
                   1943:       }else{
                   1944:         nearby = *pNext;
                   1945:       }
                   1946:       if( pPrior ) sqlitepager_unref(pPrior);
                   1947:       if( rc ){
                   1948:         clearCell(pBt, pCell);
                   1949:         return rc;
                   1950:       }
                   1951:       if( pBt->needSwab ) *pNext = swab32(*pNext);
                   1952:       pPrior = pOvfl;
                   1953:       spaceLeft = OVERFLOW_SIZE;
                   1954:       pSpace = pOvfl->aPayload;
                   1955:       pNext = &pOvfl->iNext;
                   1956:     }
                   1957:     n = nPayload;
                   1958:     if( n>spaceLeft ) n = spaceLeft;
                   1959:     memcpy(pSpace, pPayload, n);
                   1960:     nPayload -= n;
                   1961:     if( nPayload==0 && pData ){
                   1962:       pPayload = pData;
                   1963:       nPayload = nData;
                   1964:       pData = 0;
                   1965:     }else{
                   1966:       pPayload += n;
                   1967:     }
                   1968:     spaceLeft -= n;
                   1969:     pSpace += n;
                   1970:   }
                   1971:   *pNext = 0;
                   1972:   if( pPrior ){
                   1973:     sqlitepager_unref(pPrior);
                   1974:   }
                   1975:   return SQLITE_OK;
                   1976: }
                   1977: 
                   1978: /*
                   1979: ** Change the MemPage.pParent pointer on the page whose number is
                   1980: ** given in the second argument so that MemPage.pParent holds the
                   1981: ** pointer in the third argument.
                   1982: */
                   1983: static void reparentPage(Pager *pPager, Pgno pgno, MemPage *pNewParent,int idx){
                   1984:   MemPage *pThis;
                   1985: 
                   1986:   if( pgno==0 ) return;
                   1987:   assert( pPager!=0 );
                   1988:   pThis = sqlitepager_lookup(pPager, pgno);
                   1989:   if( pThis && pThis->isInit ){
                   1990:     if( pThis->pParent!=pNewParent ){
                   1991:       if( pThis->pParent ) sqlitepager_unref(pThis->pParent);
                   1992:       pThis->pParent = pNewParent;
                   1993:       if( pNewParent ) sqlitepager_ref(pNewParent);
                   1994:     }
                   1995:     pThis->idxParent = idx;
                   1996:     sqlitepager_unref(pThis);
                   1997:   }
                   1998: }
                   1999: 
                   2000: /*
                   2001: ** Reparent all children of the given page to be the given page.
                   2002: ** In other words, for every child of pPage, invoke reparentPage()
                   2003: ** to make sure that each child knows that pPage is its parent.
                   2004: **
                   2005: ** This routine gets called after you memcpy() one page into
                   2006: ** another.
                   2007: */
                   2008: static void reparentChildPages(Btree *pBt, MemPage *pPage){
                   2009:   int i;
                   2010:   Pager *pPager = pBt->pPager;
                   2011:   for(i=0; i<pPage->nCell; i++){
                   2012:     reparentPage(pPager, SWAB32(pBt, pPage->apCell[i]->h.leftChild), pPage, i);
                   2013:   }
                   2014:   reparentPage(pPager, SWAB32(pBt, pPage->u.hdr.rightChild), pPage, i);
                   2015:   pPage->idxShift = 0;
                   2016: }
                   2017: 
                   2018: /*
                   2019: ** Remove the i-th cell from pPage.  This routine effects pPage only.
                   2020: ** The cell content is not freed or deallocated.  It is assumed that
                   2021: ** the cell content has been copied someplace else.  This routine just
                   2022: ** removes the reference to the cell from pPage.
                   2023: **
                   2024: ** "sz" must be the number of bytes in the cell.
                   2025: **
                   2026: ** Do not bother maintaining the integrity of the linked list of Cells.
                   2027: ** Only the pPage->apCell[] array is important.  The relinkCellList() 
                   2028: ** routine will be called soon after this routine in order to rebuild 
                   2029: ** the linked list.
                   2030: */
                   2031: static void dropCell(Btree *pBt, MemPage *pPage, int idx, int sz){
                   2032:   int j;
                   2033:   assert( idx>=0 && idx<pPage->nCell );
                   2034:   assert( sz==cellSize(pBt, pPage->apCell[idx]) );
                   2035:   assert( sqlitepager_iswriteable(pPage) );
                   2036:   freeSpace(pBt, pPage, Addr(pPage->apCell[idx]) - Addr(pPage), sz);
                   2037:   for(j=idx; j<pPage->nCell-1; j++){
                   2038:     pPage->apCell[j] = pPage->apCell[j+1];
                   2039:   }
                   2040:   pPage->nCell--;
                   2041:   pPage->idxShift = 1;
                   2042: }
                   2043: 
                   2044: /*
                   2045: ** Insert a new cell on pPage at cell index "i".  pCell points to the
                   2046: ** content of the cell.
                   2047: **
                   2048: ** If the cell content will fit on the page, then put it there.  If it
                   2049: ** will not fit, then just make pPage->apCell[i] point to the content
                   2050: ** and set pPage->isOverfull.  
                   2051: **
                   2052: ** Do not bother maintaining the integrity of the linked list of Cells.
                   2053: ** Only the pPage->apCell[] array is important.  The relinkCellList() 
                   2054: ** routine will be called soon after this routine in order to rebuild 
                   2055: ** the linked list.
                   2056: */
                   2057: static void insertCell(Btree *pBt, MemPage *pPage, int i, Cell *pCell, int sz){
                   2058:   int idx, j;
                   2059:   assert( i>=0 && i<=pPage->nCell );
                   2060:   assert( sz==cellSize(pBt, pCell) );
                   2061:   assert( sqlitepager_iswriteable(pPage) );
                   2062:   idx = allocateSpace(pBt, pPage, sz);
                   2063:   for(j=pPage->nCell; j>i; j--){
                   2064:     pPage->apCell[j] = pPage->apCell[j-1];
                   2065:   }
                   2066:   pPage->nCell++;
                   2067:   if( idx<=0 ){
                   2068:     pPage->isOverfull = 1;
                   2069:     pPage->apCell[i] = pCell;
                   2070:   }else{
                   2071:     memcpy(&pPage->u.aDisk[idx], pCell, sz);
                   2072:     pPage->apCell[i] = (Cell*)&pPage->u.aDisk[idx];
                   2073:   }
                   2074:   pPage->idxShift = 1;
                   2075: }
                   2076: 
                   2077: /*
                   2078: ** Rebuild the linked list of cells on a page so that the cells
                   2079: ** occur in the order specified by the pPage->apCell[] array.  
                   2080: ** Invoke this routine once to repair damage after one or more
                   2081: ** invocations of either insertCell() or dropCell().
                   2082: */
                   2083: static void relinkCellList(Btree *pBt, MemPage *pPage){
                   2084:   int i;
                   2085:   u16 *pIdx;
                   2086:   assert( sqlitepager_iswriteable(pPage) );
                   2087:   pIdx = &pPage->u.hdr.firstCell;
                   2088:   for(i=0; i<pPage->nCell; i++){
                   2089:     int idx = Addr(pPage->apCell[i]) - Addr(pPage);
                   2090:     assert( idx>0 && idx<SQLITE_USABLE_SIZE );
                   2091:     *pIdx = SWAB16(pBt, idx);
                   2092:     pIdx = &pPage->apCell[i]->h.iNext;
                   2093:   }
                   2094:   *pIdx = 0;
                   2095: }
                   2096: 
                   2097: /*
                   2098: ** Make a copy of the contents of pFrom into pTo.  The pFrom->apCell[]
                   2099: ** pointers that point into pFrom->u.aDisk[] must be adjusted to point
                   2100: ** into pTo->u.aDisk[] instead.  But some pFrom->apCell[] entries might
                   2101: ** not point to pFrom->u.aDisk[].  Those are unchanged.
                   2102: */
                   2103: static void copyPage(MemPage *pTo, MemPage *pFrom){
                   2104:   uptr from, to;
                   2105:   int i;
                   2106:   memcpy(pTo->u.aDisk, pFrom->u.aDisk, SQLITE_USABLE_SIZE);
                   2107:   pTo->pParent = 0;
                   2108:   pTo->isInit = 1;
                   2109:   pTo->nCell = pFrom->nCell;
                   2110:   pTo->nFree = pFrom->nFree;
                   2111:   pTo->isOverfull = pFrom->isOverfull;
                   2112:   to = Addr(pTo);
                   2113:   from = Addr(pFrom);
                   2114:   for(i=0; i<pTo->nCell; i++){
                   2115:     uptr x = Addr(pFrom->apCell[i]);
                   2116:     if( x>from && x<from+SQLITE_USABLE_SIZE ){
                   2117:       *((uptr*)&pTo->apCell[i]) = x + to - from;
                   2118:     }else{
                   2119:       pTo->apCell[i] = pFrom->apCell[i];
                   2120:     }
                   2121:   }
                   2122: }
                   2123: 
                   2124: /*
                   2125: ** The following parameters determine how many adjacent pages get involved
                   2126: ** in a balancing operation.  NN is the number of neighbors on either side
                   2127: ** of the page that participate in the balancing operation.  NB is the
                   2128: ** total number of pages that participate, including the target page and
                   2129: ** NN neighbors on either side.
                   2130: **
                   2131: ** The minimum value of NN is 1 (of course).  Increasing NN above 1
                   2132: ** (to 2 or 3) gives a modest improvement in SELECT and DELETE performance
                   2133: ** in exchange for a larger degradation in INSERT and UPDATE performance.
                   2134: ** The value of NN appears to give the best results overall.
                   2135: */
                   2136: #define NN 1             /* Number of neighbors on either side of pPage */
                   2137: #define NB (NN*2+1)      /* Total pages involved in the balance */
                   2138: 
                   2139: /*
                   2140: ** This routine redistributes Cells on pPage and up to two siblings
                   2141: ** of pPage so that all pages have about the same amount of free space.
                   2142: ** Usually one sibling on either side of pPage is used in the balancing,
                   2143: ** though both siblings might come from one side if pPage is the first
                   2144: ** or last child of its parent.  If pPage has fewer than two siblings
                   2145: ** (something which can only happen if pPage is the root page or a 
                   2146: ** child of root) then all available siblings participate in the balancing.
                   2147: **
                   2148: ** The number of siblings of pPage might be increased or decreased by
                   2149: ** one in an effort to keep pages between 66% and 100% full. The root page
                   2150: ** is special and is allowed to be less than 66% full. If pPage is 
                   2151: ** the root page, then the depth of the tree might be increased
                   2152: ** or decreased by one, as necessary, to keep the root page from being
                   2153: ** overfull or empty.
                   2154: **
                   2155: ** This routine calls relinkCellList() on its input page regardless of
                   2156: ** whether or not it does any real balancing.  Client routines will typically
                   2157: ** invoke insertCell() or dropCell() before calling this routine, so we
                   2158: ** need to call relinkCellList() to clean up the mess that those other
                   2159: ** routines left behind.
                   2160: **
                   2161: ** pCur is left pointing to the same cell as when this routine was called
                   2162: ** even if that cell gets moved to a different page.  pCur may be NULL.
                   2163: ** Set the pCur parameter to NULL if you do not care about keeping track
                   2164: ** of a cell as that will save this routine the work of keeping track of it.
                   2165: **
                   2166: ** Note that when this routine is called, some of the Cells on pPage
                   2167: ** might not actually be stored in pPage->u.aDisk[].  This can happen
                   2168: ** if the page is overfull.  Part of the job of this routine is to
                   2169: ** make sure all Cells for pPage once again fit in pPage->u.aDisk[].
                   2170: **
                   2171: ** In the course of balancing the siblings of pPage, the parent of pPage
                   2172: ** might become overfull or underfull.  If that happens, then this routine
                   2173: ** is called recursively on the parent.
                   2174: **
                   2175: ** If this routine fails for any reason, it might leave the database
                   2176: ** in a corrupted state.  So if this routine fails, the database should
                   2177: ** be rolled back.
                   2178: */
                   2179: static int balance(Btree *pBt, MemPage *pPage, BtCursor *pCur){
                   2180:   MemPage *pParent;            /* The parent of pPage */
                   2181:   int nCell;                   /* Number of cells in apCell[] */
                   2182:   int nOld;                    /* Number of pages in apOld[] */
                   2183:   int nNew;                    /* Number of pages in apNew[] */
                   2184:   int nDiv;                    /* Number of cells in apDiv[] */
                   2185:   int i, j, k;                 /* Loop counters */
                   2186:   int idx;                     /* Index of pPage in pParent->apCell[] */
                   2187:   int nxDiv;                   /* Next divider slot in pParent->apCell[] */
                   2188:   int rc;                      /* The return code */
                   2189:   int iCur;                    /* apCell[iCur] is the cell of the cursor */
                   2190:   MemPage *pOldCurPage;        /* The cursor originally points to this page */
                   2191:   int subtotal;                /* Subtotal of bytes in cells on one page */
                   2192:   MemPage *extraUnref = 0;     /* A page that needs to be unref-ed */
                   2193:   MemPage *apOld[NB];          /* pPage and up to two siblings */
                   2194:   Pgno pgnoOld[NB];            /* Page numbers for each page in apOld[] */
                   2195:   MemPage *apNew[NB+1];        /* pPage and up to NB siblings after balancing */
                   2196:   Pgno pgnoNew[NB+1];          /* Page numbers for each page in apNew[] */
                   2197:   int idxDiv[NB];              /* Indices of divider cells in pParent */
                   2198:   Cell *apDiv[NB];             /* Divider cells in pParent */
                   2199:   Cell aTemp[NB];              /* Temporary holding area for apDiv[] */
                   2200:   int cntNew[NB+1];            /* Index in apCell[] of cell after i-th page */
                   2201:   int szNew[NB+1];             /* Combined size of cells place on i-th page */
                   2202:   MemPage aOld[NB];            /* Temporary copies of pPage and its siblings */
                   2203:   Cell *apCell[(MX_CELL+2)*NB]; /* All cells from pages being balanced */
                   2204:   int szCell[(MX_CELL+2)*NB];  /* Local size of all cells */
                   2205: 
                   2206:   /* 
                   2207:   ** Return without doing any work if pPage is neither overfull nor
                   2208:   ** underfull.
                   2209:   */
                   2210:   assert( sqlitepager_iswriteable(pPage) );
                   2211:   if( !pPage->isOverfull && pPage->nFree<SQLITE_USABLE_SIZE/2 
                   2212:         && pPage->nCell>=2){
                   2213:     relinkCellList(pBt, pPage);
                   2214:     return SQLITE_OK;
                   2215:   }
                   2216: 
                   2217:   /*
                   2218:   ** Find the parent of the page to be balanceed.
                   2219:   ** If there is no parent, it means this page is the root page and
                   2220:   ** special rules apply.
                   2221:   */
                   2222:   pParent = pPage->pParent;
                   2223:   if( pParent==0 ){
                   2224:     Pgno pgnoChild;
                   2225:     MemPage *pChild;
                   2226:     assert( pPage->isInit );
                   2227:     if( pPage->nCell==0 ){
                   2228:       if( pPage->u.hdr.rightChild ){
                   2229:         /*
                   2230:         ** The root page is empty.  Copy the one child page
                   2231:         ** into the root page and return.  This reduces the depth
                   2232:         ** of the BTree by one.
                   2233:         */
                   2234:         pgnoChild = SWAB32(pBt, pPage->u.hdr.rightChild);
                   2235:         rc = sqlitepager_get(pBt->pPager, pgnoChild, (void**)&pChild);
                   2236:         if( rc ) return rc;
                   2237:         memcpy(pPage, pChild, SQLITE_USABLE_SIZE);
                   2238:         pPage->isInit = 0;
                   2239:         rc = initPage(pBt, pPage, sqlitepager_pagenumber(pPage), 0);
                   2240:         assert( rc==SQLITE_OK );
                   2241:         reparentChildPages(pBt, pPage);
                   2242:         if( pCur && pCur->pPage==pChild ){
                   2243:           sqlitepager_unref(pChild);
                   2244:           pCur->pPage = pPage;
                   2245:           sqlitepager_ref(pPage);
                   2246:         }
                   2247:         freePage(pBt, pChild, pgnoChild);
                   2248:         sqlitepager_unref(pChild);
                   2249:       }else{
                   2250:         relinkCellList(pBt, pPage);
                   2251:       }
                   2252:       return SQLITE_OK;
                   2253:     }
                   2254:     if( !pPage->isOverfull ){
                   2255:       /* It is OK for the root page to be less than half full.
                   2256:       */
                   2257:       relinkCellList(pBt, pPage);
                   2258:       return SQLITE_OK;
                   2259:     }
                   2260:     /*
                   2261:     ** If we get to here, it means the root page is overfull.
                   2262:     ** When this happens, Create a new child page and copy the
                   2263:     ** contents of the root into the child.  Then make the root
                   2264:     ** page an empty page with rightChild pointing to the new
                   2265:     ** child.  Then fall thru to the code below which will cause
                   2266:     ** the overfull child page to be split.
                   2267:     */
                   2268:     rc = sqlitepager_write(pPage);
                   2269:     if( rc ) return rc;
                   2270:     rc = allocatePage(pBt, &pChild, &pgnoChild, sqlitepager_pagenumber(pPage));
                   2271:     if( rc ) return rc;
                   2272:     assert( sqlitepager_iswriteable(pChild) );
                   2273:     copyPage(pChild, pPage);
                   2274:     pChild->pParent = pPage;
                   2275:     pChild->idxParent = 0;
                   2276:     sqlitepager_ref(pPage);
                   2277:     pChild->isOverfull = 1;
                   2278:     if( pCur && pCur->pPage==pPage ){
                   2279:       sqlitepager_unref(pPage);
                   2280:       pCur->pPage = pChild;
                   2281:     }else{
                   2282:       extraUnref = pChild;
                   2283:     }
                   2284:     zeroPage(pBt, pPage);
                   2285:     pPage->u.hdr.rightChild = SWAB32(pBt, pgnoChild);
                   2286:     pParent = pPage;
                   2287:     pPage = pChild;
                   2288:   }
                   2289:   rc = sqlitepager_write(pParent);
                   2290:   if( rc ) return rc;
                   2291:   assert( pParent->isInit );
                   2292:   
                   2293:   /*
                   2294:   ** Find the Cell in the parent page whose h.leftChild points back
                   2295:   ** to pPage.  The "idx" variable is the index of that cell.  If pPage
                   2296:   ** is the rightmost child of pParent then set idx to pParent->nCell 
                   2297:   */
                   2298:   if( pParent->idxShift ){
                   2299:     Pgno pgno, swabPgno;
                   2300:     pgno = sqlitepager_pagenumber(pPage);
                   2301:     swabPgno = SWAB32(pBt, pgno);
                   2302:     for(idx=0; idx<pParent->nCell; idx++){
                   2303:       if( pParent->apCell[idx]->h.leftChild==swabPgno ){
                   2304:         break;
                   2305:       }
                   2306:     }
                   2307:     assert( idx<pParent->nCell || pParent->u.hdr.rightChild==swabPgno );
                   2308:   }else{
                   2309:     idx = pPage->idxParent;
                   2310:   }
                   2311: 
                   2312:   /*
                   2313:   ** Initialize variables so that it will be safe to jump
                   2314:   ** directly to balance_cleanup at any moment.
                   2315:   */
                   2316:   nOld = nNew = 0;
                   2317:   sqlitepager_ref(pParent);
                   2318: 
                   2319:   /*
                   2320:   ** Find sibling pages to pPage and the Cells in pParent that divide
                   2321:   ** the siblings.  An attempt is made to find NN siblings on either
                   2322:   ** side of pPage.  More siblings are taken from one side, however, if
                   2323:   ** pPage there are fewer than NN siblings on the other side.  If pParent
                   2324:   ** has NB or fewer children then all children of pParent are taken.
                   2325:   */
                   2326:   nxDiv = idx - NN;
                   2327:   if( nxDiv + NB > pParent->nCell ){
                   2328:     nxDiv = pParent->nCell - NB + 1;
                   2329:   }
                   2330:   if( nxDiv<0 ){
                   2331:     nxDiv = 0;
                   2332:   }
                   2333:   nDiv = 0;
                   2334:   for(i=0, k=nxDiv; i<NB; i++, k++){
                   2335:     if( k<pParent->nCell ){
                   2336:       idxDiv[i] = k;
                   2337:       apDiv[i] = pParent->apCell[k];
                   2338:       nDiv++;
                   2339:       pgnoOld[i] = SWAB32(pBt, apDiv[i]->h.leftChild);
                   2340:     }else if( k==pParent->nCell ){
                   2341:       pgnoOld[i] = SWAB32(pBt, pParent->u.hdr.rightChild);
                   2342:     }else{
                   2343:       break;
                   2344:     }
                   2345:     rc = sqlitepager_get(pBt->pPager, pgnoOld[i], (void**)&apOld[i]);
                   2346:     if( rc ) goto balance_cleanup;
                   2347:     rc = initPage(pBt, apOld[i], pgnoOld[i], pParent);
                   2348:     if( rc ) goto balance_cleanup;
                   2349:     apOld[i]->idxParent = k;
                   2350:     nOld++;
                   2351:   }
                   2352: 
                   2353:   /*
                   2354:   ** Set iCur to be the index in apCell[] of the cell that the cursor
                   2355:   ** is pointing to.  We will need this later on in order to keep the
                   2356:   ** cursor pointing at the same cell.  If pCur points to a page that
                   2357:   ** has no involvement with this rebalancing, then set iCur to a large
                   2358:   ** number so that the iCur==j tests always fail in the main cell
                   2359:   ** distribution loop below.
                   2360:   */
                   2361:   if( pCur ){
                   2362:     iCur = 0;
                   2363:     for(i=0; i<nOld; i++){
                   2364:       if( pCur->pPage==apOld[i] ){
                   2365:         iCur += pCur->idx;
                   2366:         break;
                   2367:       }
                   2368:       iCur += apOld[i]->nCell;
                   2369:       if( i<nOld-1 && pCur->pPage==pParent && pCur->idx==idxDiv[i] ){
                   2370:         break;
                   2371:       }
                   2372:       iCur++;
                   2373:     }
                   2374:     pOldCurPage = pCur->pPage;
                   2375:   }
                   2376: 
                   2377:   /*
                   2378:   ** Make copies of the content of pPage and its siblings into aOld[].
                   2379:   ** The rest of this function will use data from the copies rather
                   2380:   ** that the original pages since the original pages will be in the
                   2381:   ** process of being overwritten.
                   2382:   */
                   2383:   for(i=0; i<nOld; i++){
                   2384:     copyPage(&aOld[i], apOld[i]);
                   2385:   }
                   2386: 
                   2387:   /*
                   2388:   ** Load pointers to all cells on sibling pages and the divider cells
                   2389:   ** into the local apCell[] array.  Make copies of the divider cells
                   2390:   ** into aTemp[] and remove the the divider Cells from pParent.
                   2391:   */
                   2392:   nCell = 0;
                   2393:   for(i=0; i<nOld; i++){
                   2394:     MemPage *pOld = &aOld[i];
                   2395:     for(j=0; j<pOld->nCell; j++){
                   2396:       apCell[nCell] = pOld->apCell[j];
                   2397:       szCell[nCell] = cellSize(pBt, apCell[nCell]);
                   2398:       nCell++;
                   2399:     }
                   2400:     if( i<nOld-1 ){
                   2401:       szCell[nCell] = cellSize(pBt, apDiv[i]);
                   2402:       memcpy(&aTemp[i], apDiv[i], szCell[nCell]);
                   2403:       apCell[nCell] = &aTemp[i];
                   2404:       dropCell(pBt, pParent, nxDiv, szCell[nCell]);
                   2405:       assert( SWAB32(pBt, apCell[nCell]->h.leftChild)==pgnoOld[i] );
                   2406:       apCell[nCell]->h.leftChild = pOld->u.hdr.rightChild;
                   2407:       nCell++;
                   2408:     }
                   2409:   }
                   2410: 
                   2411:   /*
                   2412:   ** Figure out the number of pages needed to hold all nCell cells.
                   2413:   ** Store this number in "k".  Also compute szNew[] which is the total
                   2414:   ** size of all cells on the i-th page and cntNew[] which is the index
                   2415:   ** in apCell[] of the cell that divides path i from path i+1.  
                   2416:   ** cntNew[k] should equal nCell.
                   2417:   **
                   2418:   ** This little patch of code is critical for keeping the tree
                   2419:   ** balanced. 
                   2420:   */
                   2421:   for(subtotal=k=i=0; i<nCell; i++){
                   2422:     subtotal += szCell[i];
                   2423:     if( subtotal > USABLE_SPACE ){
                   2424:       szNew[k] = subtotal - szCell[i];
                   2425:       cntNew[k] = i;
                   2426:       subtotal = 0;
                   2427:       k++;
                   2428:     }
                   2429:   }
                   2430:   szNew[k] = subtotal;
                   2431:   cntNew[k] = nCell;
                   2432:   k++;
                   2433:   for(i=k-1; i>0; i--){
                   2434:     while( szNew[i]<USABLE_SPACE/2 ){
                   2435:       cntNew[i-1]--;
                   2436:       assert( cntNew[i-1]>0 );
                   2437:       szNew[i] += szCell[cntNew[i-1]];
                   2438:       szNew[i-1] -= szCell[cntNew[i-1]-1];
                   2439:     }
                   2440:   }
                   2441:   assert( cntNew[0]>0 );
                   2442: 
                   2443:   /*
                   2444:   ** Allocate k new pages.  Reuse old pages where possible.
                   2445:   */
                   2446:   for(i=0; i<k; i++){
                   2447:     if( i<nOld ){
                   2448:       apNew[i] = apOld[i];
                   2449:       pgnoNew[i] = pgnoOld[i];
                   2450:       apOld[i] = 0;
                   2451:       sqlitepager_write(apNew[i]);
                   2452:     }else{
                   2453:       rc = allocatePage(pBt, &apNew[i], &pgnoNew[i], pgnoNew[i-1]);
                   2454:       if( rc ) goto balance_cleanup;
                   2455:     }
                   2456:     nNew++;
                   2457:     zeroPage(pBt, apNew[i]);
                   2458:     apNew[i]->isInit = 1;
                   2459:   }
                   2460: 
                   2461:   /* Free any old pages that were not reused as new pages.
                   2462:   */
                   2463:   while( i<nOld ){
                   2464:     rc = freePage(pBt, apOld[i], pgnoOld[i]);
                   2465:     if( rc ) goto balance_cleanup;
                   2466:     sqlitepager_unref(apOld[i]);
                   2467:     apOld[i] = 0;
                   2468:     i++;
                   2469:   }
                   2470: 
                   2471:   /*
                   2472:   ** Put the new pages in accending order.  This helps to
                   2473:   ** keep entries in the disk file in order so that a scan
                   2474:   ** of the table is a linear scan through the file.  That
                   2475:   ** in turn helps the operating system to deliver pages
                   2476:   ** from the disk more rapidly.
                   2477:   **
                   2478:   ** An O(n^2) insertion sort algorithm is used, but since
                   2479:   ** n is never more than NB (a small constant), that should
                   2480:   ** not be a problem.
                   2481:   **
                   2482:   ** When NB==3, this one optimization makes the database
                   2483:   ** about 25% faster for large insertions and deletions.
                   2484:   */
                   2485:   for(i=0; i<k-1; i++){
                   2486:     int minV = pgnoNew[i];
                   2487:     int minI = i;
                   2488:     for(j=i+1; j<k; j++){
                   2489:       if( pgnoNew[j]<(unsigned)minV ){
                   2490:         minI = j;
                   2491:         minV = pgnoNew[j];
                   2492:       }
                   2493:     }
                   2494:     if( minI>i ){
                   2495:       int t;
                   2496:       MemPage *pT;
                   2497:       t = pgnoNew[i];
                   2498:       pT = apNew[i];
                   2499:       pgnoNew[i] = pgnoNew[minI];
                   2500:       apNew[i] = apNew[minI];
                   2501:       pgnoNew[minI] = t;
                   2502:       apNew[minI] = pT;
                   2503:     }
                   2504:   }
                   2505: 
                   2506:   /*
                   2507:   ** Evenly distribute the data in apCell[] across the new pages.
                   2508:   ** Insert divider cells into pParent as necessary.
                   2509:   */
                   2510:   j = 0;
                   2511:   for(i=0; i<nNew; i++){
                   2512:     MemPage *pNew = apNew[i];
                   2513:     while( j<cntNew[i] ){
                   2514:       assert( pNew->nFree>=szCell[j] );
                   2515:       if( pCur && iCur==j ){ pCur->pPage = pNew; pCur->idx = pNew->nCell; }
                   2516:       insertCell(pBt, pNew, pNew->nCell, apCell[j], szCell[j]);
                   2517:       j++;
                   2518:     }
                   2519:     assert( pNew->nCell>0 );
                   2520:     assert( !pNew->isOverfull );
                   2521:     relinkCellList(pBt, pNew);
                   2522:     if( i<nNew-1 && j<nCell ){
                   2523:       pNew->u.hdr.rightChild = apCell[j]->h.leftChild;
                   2524:       apCell[j]->h.leftChild = SWAB32(pBt, pgnoNew[i]);
                   2525:       if( pCur && iCur==j ){ pCur->pPage = pParent; pCur->idx = nxDiv; }
                   2526:       insertCell(pBt, pParent, nxDiv, apCell[j], szCell[j]);
                   2527:       j++;
                   2528:       nxDiv++;
                   2529:     }
                   2530:   }
                   2531:   assert( j==nCell );
                   2532:   apNew[nNew-1]->u.hdr.rightChild = aOld[nOld-1].u.hdr.rightChild;
                   2533:   if( nxDiv==pParent->nCell ){
                   2534:     pParent->u.hdr.rightChild = SWAB32(pBt, pgnoNew[nNew-1]);
                   2535:   }else{
                   2536:     pParent->apCell[nxDiv]->h.leftChild = SWAB32(pBt, pgnoNew[nNew-1]);
                   2537:   }
                   2538:   if( pCur ){
                   2539:     if( j<=iCur && pCur->pPage==pParent && pCur->idx>idxDiv[nOld-1] ){
                   2540:       assert( pCur->pPage==pOldCurPage );
                   2541:       pCur->idx += nNew - nOld;
                   2542:     }else{
                   2543:       assert( pOldCurPage!=0 );
                   2544:       sqlitepager_ref(pCur->pPage);
                   2545:       sqlitepager_unref(pOldCurPage);
                   2546:     }
                   2547:   }
                   2548: 
                   2549:   /*
                   2550:   ** Reparent children of all cells.
                   2551:   */
                   2552:   for(i=0; i<nNew; i++){
                   2553:     reparentChildPages(pBt, apNew[i]);
                   2554:   }
                   2555:   reparentChildPages(pBt, pParent);
                   2556: 
                   2557:   /*
                   2558:   ** balance the parent page.
                   2559:   */
                   2560:   rc = balance(pBt, pParent, pCur);
                   2561: 
                   2562:   /*
                   2563:   ** Cleanup before returning.
                   2564:   */
                   2565: balance_cleanup:
                   2566:   if( extraUnref ){
                   2567:     sqlitepager_unref(extraUnref);
                   2568:   }
                   2569:   for(i=0; i<nOld; i++){
                   2570:     if( apOld[i]!=0 && apOld[i]!=&aOld[i] ) sqlitepager_unref(apOld[i]);
                   2571:   }
                   2572:   for(i=0; i<nNew; i++){
                   2573:     sqlitepager_unref(apNew[i]);
                   2574:   }
                   2575:   if( pCur && pCur->pPage==0 ){
                   2576:     pCur->pPage = pParent;
                   2577:     pCur->idx = 0;
                   2578:   }else{
                   2579:     sqlitepager_unref(pParent);
                   2580:   }
                   2581:   return rc;
                   2582: }
                   2583: 
                   2584: /*
                   2585: ** This routine checks all cursors that point to the same table
                   2586: ** as pCur points to.  If any of those cursors were opened with
                   2587: ** wrFlag==0 then this routine returns SQLITE_LOCKED.  If all
                   2588: ** cursors point to the same table were opened with wrFlag==1
                   2589: ** then this routine returns SQLITE_OK.
                   2590: **
                   2591: ** In addition to checking for read-locks (where a read-lock 
                   2592: ** means a cursor opened with wrFlag==0) this routine also moves
                   2593: ** all cursors other than pCur so that they are pointing to the 
                   2594: ** first Cell on root page.  This is necessary because an insert 
                   2595: ** or delete might change the number of cells on a page or delete
                   2596: ** a page entirely and we do not want to leave any cursors 
                   2597: ** pointing to non-existant pages or cells.
                   2598: */
                   2599: static int checkReadLocks(BtCursor *pCur){
                   2600:   BtCursor *p;
                   2601:   assert( pCur->wrFlag );
                   2602:   for(p=pCur->pShared; p!=pCur; p=p->pShared){
                   2603:     assert( p );
                   2604:     assert( p->pgnoRoot==pCur->pgnoRoot );
                   2605:     if( p->wrFlag==0 ) return SQLITE_LOCKED;
                   2606:     if( sqlitepager_pagenumber(p->pPage)!=p->pgnoRoot ){
                   2607:       moveToRoot(p);
                   2608:     }
                   2609:   }
                   2610:   return SQLITE_OK;
                   2611: }
                   2612: 
                   2613: /*
                   2614: ** Insert a new record into the BTree.  The key is given by (pKey,nKey)
                   2615: ** and the data is given by (pData,nData).  The cursor is used only to
                   2616: ** define what database the record should be inserted into.  The cursor
                   2617: ** is left pointing at the new record.
                   2618: */
                   2619: static int fileBtreeInsert(
                   2620:   BtCursor *pCur,                /* Insert data into the table of this cursor */
                   2621:   const void *pKey, int nKey,    /* The key of the new record */
                   2622:   const void *pData, int nData   /* The data of the new record */
                   2623: ){
                   2624:   Cell newCell;
                   2625:   int rc;
                   2626:   int loc;
                   2627:   int szNew;
                   2628:   MemPage *pPage;
                   2629:   Btree *pBt = pCur->pBt;
                   2630: 
                   2631:   if( pCur->pPage==0 ){
                   2632:     return SQLITE_ABORT;  /* A rollback destroyed this cursor */
                   2633:   }
                   2634:   if( !pBt->inTrans || nKey+nData==0 ){
                   2635:     /* Must start a transaction before doing an insert */
                   2636:     return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
                   2637:   }
                   2638:   assert( !pBt->readOnly );
                   2639:   if( !pCur->wrFlag ){
                   2640:     return SQLITE_PERM;   /* Cursor not open for writing */
                   2641:   }
                   2642:   if( checkReadLocks(pCur) ){
                   2643:     return SQLITE_LOCKED; /* The table pCur points to has a read lock */
                   2644:   }
                   2645:   rc = fileBtreeMoveto(pCur, pKey, nKey, &loc);
                   2646:   if( rc ) return rc;
                   2647:   pPage = pCur->pPage;
                   2648:   assert( pPage->isInit );
                   2649:   rc = sqlitepager_write(pPage);
                   2650:   if( rc ) return rc;
                   2651:   rc = fillInCell(pBt, &newCell, pKey, nKey, pData, nData);
                   2652:   if( rc ) return rc;
                   2653:   szNew = cellSize(pBt, &newCell);
                   2654:   if( loc==0 ){
                   2655:     newCell.h.leftChild = pPage->apCell[pCur->idx]->h.leftChild;
                   2656:     rc = clearCell(pBt, pPage->apCell[pCur->idx]);
                   2657:     if( rc ) return rc;
                   2658:     dropCell(pBt, pPage, pCur->idx, cellSize(pBt, pPage->apCell[pCur->idx]));
                   2659:   }else if( loc<0 && pPage->nCell>0 ){
                   2660:     assert( pPage->u.hdr.rightChild==0 );  /* Must be a leaf page */
                   2661:     pCur->idx++;
                   2662:   }else{
                   2663:     assert( pPage->u.hdr.rightChild==0 );  /* Must be a leaf page */
                   2664:   }
                   2665:   insertCell(pBt, pPage, pCur->idx, &newCell, szNew);
                   2666:   rc = balance(pCur->pBt, pPage, pCur);
                   2667:   /* sqliteBtreePageDump(pCur->pBt, pCur->pgnoRoot, 1); */
                   2668:   /* fflush(stdout); */
                   2669:   pCur->eSkip = SKIP_INVALID;
                   2670:   return rc;
                   2671: }
                   2672: 
                   2673: /*
                   2674: ** Delete the entry that the cursor is pointing to.
                   2675: **
                   2676: ** The cursor is left pointing at either the next or the previous
                   2677: ** entry.  If the cursor is left pointing to the next entry, then 
                   2678: ** the pCur->eSkip flag is set to SKIP_NEXT which forces the next call to 
                   2679: ** sqliteBtreeNext() to be a no-op.  That way, you can always call
                   2680: ** sqliteBtreeNext() after a delete and the cursor will be left
                   2681: ** pointing to the first entry after the deleted entry.  Similarly,
                   2682: ** pCur->eSkip is set to SKIP_PREV is the cursor is left pointing to
                   2683: ** the entry prior to the deleted entry so that a subsequent call to
                   2684: ** sqliteBtreePrevious() will always leave the cursor pointing at the
                   2685: ** entry immediately before the one that was deleted.
                   2686: */
                   2687: static int fileBtreeDelete(BtCursor *pCur){
                   2688:   MemPage *pPage = pCur->pPage;
                   2689:   Cell *pCell;
                   2690:   int rc;
                   2691:   Pgno pgnoChild;
                   2692:   Btree *pBt = pCur->pBt;
                   2693: 
                   2694:   assert( pPage->isInit );
                   2695:   if( pCur->pPage==0 ){
                   2696:     return SQLITE_ABORT;  /* A rollback destroyed this cursor */
                   2697:   }
                   2698:   if( !pBt->inTrans ){
                   2699:     /* Must start a transaction before doing a delete */
                   2700:     return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
                   2701:   }
                   2702:   assert( !pBt->readOnly );
                   2703:   if( pCur->idx >= pPage->nCell ){
                   2704:     return SQLITE_ERROR;  /* The cursor is not pointing to anything */
                   2705:   }
                   2706:   if( !pCur->wrFlag ){
                   2707:     return SQLITE_PERM;   /* Did not open this cursor for writing */
                   2708:   }
                   2709:   if( checkReadLocks(pCur) ){
                   2710:     return SQLITE_LOCKED; /* The table pCur points to has a read lock */
                   2711:   }
                   2712:   rc = sqlitepager_write(pPage);
                   2713:   if( rc ) return rc;
                   2714:   pCell = pPage->apCell[pCur->idx];
                   2715:   pgnoChild = SWAB32(pBt, pCell->h.leftChild);
                   2716:   clearCell(pBt, pCell);
                   2717:   if( pgnoChild ){
                   2718:     /*
                   2719:     ** The entry we are about to delete is not a leaf so if we do not
                   2720:     ** do something we will leave a hole on an internal page.
                   2721:     ** We have to fill the hole by moving in a cell from a leaf.  The
                   2722:     ** next Cell after the one to be deleted is guaranteed to exist and
                   2723:     ** to be a leaf so we can use it.
                   2724:     */
                   2725:     BtCursor leafCur;
                   2726:     Cell *pNext;
                   2727:     int szNext;
                   2728:     int notUsed;
                   2729:     getTempCursor(pCur, &leafCur);
                   2730:     rc = fileBtreeNext(&leafCur, &notUsed);
                   2731:     if( rc!=SQLITE_OK ){
                   2732:       if( rc!=SQLITE_NOMEM ) rc = SQLITE_CORRUPT;
                   2733:       return rc;
                   2734:     }
                   2735:     rc = sqlitepager_write(leafCur.pPage);
                   2736:     if( rc ) return rc;
                   2737:     dropCell(pBt, pPage, pCur->idx, cellSize(pBt, pCell));
                   2738:     pNext = leafCur.pPage->apCell[leafCur.idx];
                   2739:     szNext = cellSize(pBt, pNext);
                   2740:     pNext->h.leftChild = SWAB32(pBt, pgnoChild);
                   2741:     insertCell(pBt, pPage, pCur->idx, pNext, szNext);
                   2742:     rc = balance(pBt, pPage, pCur);
                   2743:     if( rc ) return rc;
                   2744:     pCur->eSkip = SKIP_NEXT;
                   2745:     dropCell(pBt, leafCur.pPage, leafCur.idx, szNext);
                   2746:     rc = balance(pBt, leafCur.pPage, pCur);
                   2747:     releaseTempCursor(&leafCur);
                   2748:   }else{
                   2749:     dropCell(pBt, pPage, pCur->idx, cellSize(pBt, pCell));
                   2750:     if( pCur->idx>=pPage->nCell ){
                   2751:       pCur->idx = pPage->nCell-1;
                   2752:       if( pCur->idx<0 ){ 
                   2753:         pCur->idx = 0;
                   2754:         pCur->eSkip = SKIP_NEXT;
                   2755:       }else{
                   2756:         pCur->eSkip = SKIP_PREV;
                   2757:       }
                   2758:     }else{
                   2759:       pCur->eSkip = SKIP_NEXT;
                   2760:     }
                   2761:     rc = balance(pBt, pPage, pCur);
                   2762:   }
                   2763:   return rc;
                   2764: }
                   2765: 
                   2766: /*
                   2767: ** Create a new BTree table.  Write into *piTable the page
                   2768: ** number for the root page of the new table.
                   2769: **
                   2770: ** In the current implementation, BTree tables and BTree indices are the 
                   2771: ** the same.  In the future, we may change this so that BTree tables
                   2772: ** are restricted to having a 4-byte integer key and arbitrary data and
                   2773: ** BTree indices are restricted to having an arbitrary key and no data.
                   2774: ** But for now, this routine also serves to create indices.
                   2775: */
                   2776: static int fileBtreeCreateTable(Btree *pBt, int *piTable){
                   2777:   MemPage *pRoot;
                   2778:   Pgno pgnoRoot;
                   2779:   int rc;
                   2780:   if( !pBt->inTrans ){
                   2781:     /* Must start a transaction first */
                   2782:     return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
                   2783:   }
                   2784:   if( pBt->readOnly ){
                   2785:     return SQLITE_READONLY;
                   2786:   }
                   2787:   rc = allocatePage(pBt, &pRoot, &pgnoRoot, 0);
                   2788:   if( rc ) return rc;
                   2789:   assert( sqlitepager_iswriteable(pRoot) );
                   2790:   zeroPage(pBt, pRoot);
                   2791:   sqlitepager_unref(pRoot);
                   2792:   *piTable = (int)pgnoRoot;
                   2793:   return SQLITE_OK;
                   2794: }
                   2795: 
                   2796: /*
                   2797: ** Erase the given database page and all its children.  Return
                   2798: ** the page to the freelist.
                   2799: */
                   2800: static int clearDatabasePage(Btree *pBt, Pgno pgno, int freePageFlag){
                   2801:   MemPage *pPage;
                   2802:   int rc;
                   2803:   Cell *pCell;
                   2804:   int idx;
                   2805: 
                   2806:   rc = sqlitepager_get(pBt->pPager, pgno, (void**)&pPage);
                   2807:   if( rc ) return rc;
                   2808:   rc = sqlitepager_write(pPage);
                   2809:   if( rc ) return rc;
                   2810:   rc = initPage(pBt, pPage, pgno, 0);
                   2811:   if( rc ) return rc;
                   2812:   idx = SWAB16(pBt, pPage->u.hdr.firstCell);
                   2813:   while( idx>0 ){
                   2814:     pCell = (Cell*)&pPage->u.aDisk[idx];
                   2815:     idx = SWAB16(pBt, pCell->h.iNext);
                   2816:     if( pCell->h.leftChild ){
                   2817:       rc = clearDatabasePage(pBt, SWAB32(pBt, pCell->h.leftChild), 1);
                   2818:       if( rc ) return rc;
                   2819:     }
                   2820:     rc = clearCell(pBt, pCell);
                   2821:     if( rc ) return rc;
                   2822:   }
                   2823:   if( pPage->u.hdr.rightChild ){
                   2824:     rc = clearDatabasePage(pBt, SWAB32(pBt, pPage->u.hdr.rightChild), 1);
                   2825:     if( rc ) return rc;
                   2826:   }
                   2827:   if( freePageFlag ){
                   2828:     rc = freePage(pBt, pPage, pgno);
                   2829:   }else{
                   2830:     zeroPage(pBt, pPage);
                   2831:   }
                   2832:   sqlitepager_unref(pPage);
                   2833:   return rc;
                   2834: }
                   2835: 
                   2836: /*
                   2837: ** Delete all information from a single table in the database.
                   2838: */
                   2839: static int fileBtreeClearTable(Btree *pBt, int iTable){
                   2840:   int rc;
                   2841:   BtCursor *pCur;
                   2842:   if( !pBt->inTrans ){
                   2843:     return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
                   2844:   }
                   2845:   for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
                   2846:     if( pCur->pgnoRoot==(Pgno)iTable ){
                   2847:       if( pCur->wrFlag==0 ) return SQLITE_LOCKED;
                   2848:       moveToRoot(pCur);
                   2849:     }
                   2850:   }
                   2851:   rc = clearDatabasePage(pBt, (Pgno)iTable, 0);
                   2852:   if( rc ){
                   2853:     fileBtreeRollback(pBt);
                   2854:   }
                   2855:   return rc;
                   2856: }
                   2857: 
                   2858: /*
                   2859: ** Erase all information in a table and add the root of the table to
                   2860: ** the freelist.  Except, the root of the principle table (the one on
                   2861: ** page 2) is never added to the freelist.
                   2862: */
                   2863: static int fileBtreeDropTable(Btree *pBt, int iTable){
                   2864:   int rc;
                   2865:   MemPage *pPage;
                   2866:   BtCursor *pCur;
                   2867:   if( !pBt->inTrans ){
                   2868:     return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
                   2869:   }
                   2870:   for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){
                   2871:     if( pCur->pgnoRoot==(Pgno)iTable ){
                   2872:       return SQLITE_LOCKED;  /* Cannot drop a table that has a cursor */
                   2873:     }
                   2874:   }
                   2875:   rc = sqlitepager_get(pBt->pPager, (Pgno)iTable, (void**)&pPage);
                   2876:   if( rc ) return rc;
                   2877:   rc = fileBtreeClearTable(pBt, iTable);
                   2878:   if( rc ) return rc;
                   2879:   if( iTable>2 ){
                   2880:     rc = freePage(pBt, pPage, iTable);
                   2881:   }else{
                   2882:     zeroPage(pBt, pPage);
                   2883:   }
                   2884:   sqlitepager_unref(pPage);
                   2885:   return rc;  
                   2886: }
                   2887: 
                   2888: #if 0 /* UNTESTED */
                   2889: /*
                   2890: ** Copy all cell data from one database file into another.
                   2891: ** pages back the freelist.
                   2892: */
                   2893: static int copyCell(Btree *pBtFrom, BTree *pBtTo, Cell *pCell){
                   2894:   Pager *pFromPager = pBtFrom->pPager;
                   2895:   OverflowPage *pOvfl;
                   2896:   Pgno ovfl, nextOvfl;
                   2897:   Pgno *pPrev;
                   2898:   int rc = SQLITE_OK;
                   2899:   MemPage *pNew, *pPrevPg;
                   2900:   Pgno new;
                   2901: 
                   2902:   if( NKEY(pBtTo, pCell->h) + NDATA(pBtTo, pCell->h) <= MX_LOCAL_PAYLOAD ){
                   2903:     return SQLITE_OK;
                   2904:   }
                   2905:   pPrev = &pCell->ovfl;
                   2906:   pPrevPg = 0;
                   2907:   ovfl = SWAB32(pBtTo, pCell->ovfl);
                   2908:   while( ovfl && rc==SQLITE_OK ){
                   2909:     rc = sqlitepager_get(pFromPager, ovfl, (void**)&pOvfl);
                   2910:     if( rc ) return rc;
                   2911:     nextOvfl = SWAB32(pBtFrom, pOvfl->iNext);
                   2912:     rc = allocatePage(pBtTo, &pNew, &new, 0);
                   2913:     if( rc==SQLITE_OK ){
                   2914:       rc = sqlitepager_write(pNew);
                   2915:       if( rc==SQLITE_OK ){
                   2916:         memcpy(pNew, pOvfl, SQLITE_USABLE_SIZE);
                   2917:         *pPrev = SWAB32(pBtTo, new);
                   2918:         if( pPrevPg ){
                   2919:           sqlitepager_unref(pPrevPg);
                   2920:         }
                   2921:         pPrev = &pOvfl->iNext;
                   2922:         pPrevPg = pNew;
                   2923:       }
                   2924:     }
                   2925:     sqlitepager_unref(pOvfl);
                   2926:     ovfl = nextOvfl;
                   2927:   }
                   2928:   if( pPrevPg ){
                   2929:     sqlitepager_unref(pPrevPg);
                   2930:   }
                   2931:   return rc;
                   2932: }
                   2933: #endif
                   2934: 
                   2935: 
                   2936: #if 0 /* UNTESTED */
                   2937: /*
                   2938: ** Copy a page of data from one database over to another.
                   2939: */
                   2940: static int copyDatabasePage(
                   2941:   Btree *pBtFrom,
                   2942:   Pgno pgnoFrom,
                   2943:   Btree *pBtTo,
                   2944:   Pgno *pTo
                   2945: ){
                   2946:   MemPage *pPageFrom, *pPage;
                   2947:   Pgno to;
                   2948:   int rc;
                   2949:   Cell *pCell;
                   2950:   int idx;
                   2951: 
                   2952:   rc = sqlitepager_get(pBtFrom->pPager, pgno, (void**)&pPageFrom);
                   2953:   if( rc ) return rc;
                   2954:   rc = allocatePage(pBt, &pPage, pTo, 0);
                   2955:   if( rc==SQLITE_OK ){
                   2956:     rc = sqlitepager_write(pPage);
                   2957:   }
                   2958:   if( rc==SQLITE_OK ){
                   2959:     memcpy(pPage, pPageFrom, SQLITE_USABLE_SIZE);
                   2960:     idx = SWAB16(pBt, pPage->u.hdr.firstCell);
                   2961:     while( idx>0 ){
                   2962:       pCell = (Cell*)&pPage->u.aDisk[idx];
                   2963:       idx = SWAB16(pBt, pCell->h.iNext);
                   2964:       if( pCell->h.leftChild ){
                   2965:         Pgno newChld;
                   2966:         rc = copyDatabasePage(pBtFrom, SWAB32(pBtFrom, pCell->h.leftChild),
                   2967:                               pBtTo, &newChld);
                   2968:         if( rc ) return rc;
                   2969:         pCell->h.leftChild = SWAB32(pBtFrom, newChld);
                   2970:       }
                   2971:       rc = copyCell(pBtFrom, pBtTo, pCell);
                   2972:       if( rc ) return rc;
                   2973:     }
                   2974:     if( pPage->u.hdr.rightChild ){
                   2975:       Pgno newChld;
                   2976:       rc = copyDatabasePage(pBtFrom, SWAB32(pBtFrom, pPage->u.hdr.rightChild), 
                   2977:                             pBtTo, &newChld);
                   2978:       if( rc ) return rc;
                   2979:       pPage->u.hdr.rightChild = SWAB32(pBtTo, newChild);
                   2980:     }
                   2981:   }
                   2982:   sqlitepager_unref(pPage);
                   2983:   return rc;
                   2984: }
                   2985: #endif
                   2986: 
                   2987: /*
                   2988: ** Read the meta-information out of a database file.
                   2989: */
                   2990: static int fileBtreeGetMeta(Btree *pBt, int *aMeta){
                   2991:   PageOne *pP1;
                   2992:   int rc;
                   2993:   int i;
                   2994: 
                   2995:   rc = sqlitepager_get(pBt->pPager, 1, (void**)&pP1);
                   2996:   if( rc ) return rc;
                   2997:   aMeta[0] = SWAB32(pBt, pP1->nFree);
                   2998:   for(i=0; i<sizeof(pP1->aMeta)/sizeof(pP1->aMeta[0]); i++){
                   2999:     aMeta[i+1] = SWAB32(pBt, pP1->aMeta[i]);
                   3000:   }
                   3001:   sqlitepager_unref(pP1);
                   3002:   return SQLITE_OK;
                   3003: }
                   3004: 
                   3005: /*
                   3006: ** Write meta-information back into the database.
                   3007: */
                   3008: static int fileBtreeUpdateMeta(Btree *pBt, int *aMeta){
                   3009:   PageOne *pP1;
                   3010:   int rc, i;
                   3011:   if( !pBt->inTrans ){
                   3012:     return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
                   3013:   }
                   3014:   pP1 = pBt->page1;
                   3015:   rc = sqlitepager_write(pP1);
                   3016:   if( rc ) return rc;   
                   3017:   for(i=0; i<sizeof(pP1->aMeta)/sizeof(pP1->aMeta[0]); i++){
                   3018:     pP1->aMeta[i] = SWAB32(pBt, aMeta[i+1]);
                   3019:   }
                   3020:   return SQLITE_OK;
                   3021: }
                   3022: 
                   3023: /******************************************************************************
                   3024: ** The complete implementation of the BTree subsystem is above this line.
                   3025: ** All the code the follows is for testing and troubleshooting the BTree
                   3026: ** subsystem.  None of the code that follows is used during normal operation.
                   3027: ******************************************************************************/
                   3028: 
                   3029: /*
                   3030: ** Print a disassembly of the given page on standard output.  This routine
                   3031: ** is used for debugging and testing only.
                   3032: */
                   3033: #ifdef SQLITE_TEST
                   3034: static int fileBtreePageDump(Btree *pBt, int pgno, int recursive){
                   3035:   int rc;
                   3036:   MemPage *pPage;
                   3037:   int i, j;
                   3038:   int nFree;
                   3039:   u16 idx;
                   3040:   char range[20];
                   3041:   unsigned char payload[20];
                   3042:   rc = sqlitepager_get(pBt->pPager, (Pgno)pgno, (void**)&pPage);
                   3043:   if( rc ){
                   3044:     return rc;
                   3045:   }
                   3046:   if( recursive ) printf("PAGE %d:\n", pgno);
                   3047:   i = 0;
                   3048:   idx = SWAB16(pBt, pPage->u.hdr.firstCell);
                   3049:   while( idx>0 && idx<=SQLITE_USABLE_SIZE-MIN_CELL_SIZE ){
                   3050:     Cell *pCell = (Cell*)&pPage->u.aDisk[idx];
                   3051:     int sz = cellSize(pBt, pCell);
                   3052:     sprintf(range,"%d..%d", idx, idx+sz-1);
                   3053:     sz = NKEY(pBt, pCell->h) + NDATA(pBt, pCell->h);
                   3054:     if( sz>sizeof(payload)-1 ) sz = sizeof(payload)-1;
                   3055:     memcpy(payload, pCell->aPayload, sz);
                   3056:     for(j=0; j<sz; j++){
                   3057:       if( payload[j]<0x20 || payload[j]>0x7f ) payload[j] = '.';
                   3058:     }
                   3059:     payload[sz] = 0;
                   3060:     printf(
                   3061:       "cell %2d: i=%-10s chld=%-4d nk=%-4d nd=%-4d payload=%s\n",
                   3062:       i, range, (int)pCell->h.leftChild, 
                   3063:       NKEY(pBt, pCell->h), NDATA(pBt, pCell->h),
                   3064:       payload
                   3065:     );
                   3066:     if( pPage->isInit && pPage->apCell[i]!=pCell ){
                   3067:       printf("**** apCell[%d] does not match on prior entry ****\n", i);
                   3068:     }
                   3069:     i++;
                   3070:     idx = SWAB16(pBt, pCell->h.iNext);
                   3071:   }
                   3072:   if( idx!=0 ){
                   3073:     printf("ERROR: next cell index out of range: %d\n", idx);
                   3074:   }
                   3075:   printf("right_child: %d\n", SWAB32(pBt, pPage->u.hdr.rightChild));
                   3076:   nFree = 0;
                   3077:   i = 0;
                   3078:   idx = SWAB16(pBt, pPage->u.hdr.firstFree);
                   3079:   while( idx>0 && idx<SQLITE_USABLE_SIZE ){
                   3080:     FreeBlk *p = (FreeBlk*)&pPage->u.aDisk[idx];
                   3081:     sprintf(range,"%d..%d", idx, idx+p->iSize-1);
                   3082:     nFree += SWAB16(pBt, p->iSize);
                   3083:     printf("freeblock %2d: i=%-10s size=%-4d total=%d\n",
                   3084:        i, range, SWAB16(pBt, p->iSize), nFree);
                   3085:     idx = SWAB16(pBt, p->iNext);
                   3086:     i++;
                   3087:   }
                   3088:   if( idx!=0 ){
                   3089:     printf("ERROR: next freeblock index out of range: %d\n", idx);
                   3090:   }
                   3091:   if( recursive && pPage->u.hdr.rightChild!=0 ){
                   3092:     idx = SWAB16(pBt, pPage->u.hdr.firstCell);
                   3093:     while( idx>0 && idx<SQLITE_USABLE_SIZE-MIN_CELL_SIZE ){
                   3094:       Cell *pCell = (Cell*)&pPage->u.aDisk[idx];
                   3095:       fileBtreePageDump(pBt, SWAB32(pBt, pCell->h.leftChild), 1);
                   3096:       idx = SWAB16(pBt, pCell->h.iNext);
                   3097:     }
                   3098:     fileBtreePageDump(pBt, SWAB32(pBt, pPage->u.hdr.rightChild), 1);
                   3099:   }
                   3100:   sqlitepager_unref(pPage);
                   3101:   return SQLITE_OK;
                   3102: }
                   3103: #endif
                   3104: 
                   3105: #ifdef SQLITE_TEST
                   3106: /*
                   3107: ** Fill aResult[] with information about the entry and page that the
                   3108: ** cursor is pointing to.
                   3109: ** 
                   3110: **   aResult[0] =  The page number
                   3111: **   aResult[1] =  The entry number
                   3112: **   aResult[2] =  Total number of entries on this page
                   3113: **   aResult[3] =  Size of this entry
                   3114: **   aResult[4] =  Number of free bytes on this page
                   3115: **   aResult[5] =  Number of free blocks on the page
                   3116: **   aResult[6] =  Page number of the left child of this entry
                   3117: **   aResult[7] =  Page number of the right child for the whole page
                   3118: **
                   3119: ** This routine is used for testing and debugging only.
                   3120: */
                   3121: static int fileBtreeCursorDump(BtCursor *pCur, int *aResult){
                   3122:   int cnt, idx;
                   3123:   MemPage *pPage = pCur->pPage;
                   3124:   Btree *pBt = pCur->pBt;
                   3125:   aResult[0] = sqlitepager_pagenumber(pPage);
                   3126:   aResult[1] = pCur->idx;
                   3127:   aResult[2] = pPage->nCell;
                   3128:   if( pCur->idx>=0 && pCur->idx<pPage->nCell ){
                   3129:     aResult[3] = cellSize(pBt, pPage->apCell[pCur->idx]);
                   3130:     aResult[6] = SWAB32(pBt, pPage->apCell[pCur->idx]->h.leftChild);
                   3131:   }else{
                   3132:     aResult[3] = 0;
                   3133:     aResult[6] = 0;
                   3134:   }
                   3135:   aResult[4] = pPage->nFree;
                   3136:   cnt = 0;
                   3137:   idx = SWAB16(pBt, pPage->u.hdr.firstFree);
                   3138:   while( idx>0 && idx<SQLITE_USABLE_SIZE ){
                   3139:     cnt++;
                   3140:     idx = SWAB16(pBt, ((FreeBlk*)&pPage->u.aDisk[idx])->iNext);
                   3141:   }
                   3142:   aResult[5] = cnt;
                   3143:   aResult[7] = SWAB32(pBt, pPage->u.hdr.rightChild);
                   3144:   return SQLITE_OK;
                   3145: }
                   3146: #endif
                   3147: 
                   3148: /*
                   3149: ** Return the pager associated with a BTree.  This routine is used for
                   3150: ** testing and debugging only.
                   3151: */
                   3152: static Pager *fileBtreePager(Btree *pBt){
                   3153:   return pBt->pPager;
                   3154: }
                   3155: 
                   3156: /*
                   3157: ** This structure is passed around through all the sanity checking routines
                   3158: ** in order to keep track of some global state information.
                   3159: */
                   3160: typedef struct IntegrityCk IntegrityCk;
                   3161: struct IntegrityCk {
                   3162:   Btree *pBt;    /* The tree being checked out */
                   3163:   Pager *pPager; /* The associated pager.  Also accessible by pBt->pPager */
                   3164:   int nPage;     /* Number of pages in the database */
                   3165:   int *anRef;    /* Number of times each page is referenced */
                   3166:   char *zErrMsg; /* An error message.  NULL of no errors seen. */
                   3167: };
                   3168: 
                   3169: /*
                   3170: ** Append a message to the error message string.
                   3171: */
                   3172: static void checkAppendMsg(IntegrityCk *pCheck, char *zMsg1, char *zMsg2){
                   3173:   if( pCheck->zErrMsg ){
                   3174:     char *zOld = pCheck->zErrMsg;
                   3175:     pCheck->zErrMsg = 0;
                   3176:     sqliteSetString(&pCheck->zErrMsg, zOld, "\n", zMsg1, zMsg2, (char*)0);
                   3177:     sqliteFree(zOld);
                   3178:   }else{
                   3179:     sqliteSetString(&pCheck->zErrMsg, zMsg1, zMsg2, (char*)0);
                   3180:   }
                   3181: }
                   3182: 
                   3183: /*
                   3184: ** Add 1 to the reference count for page iPage.  If this is the second
                   3185: ** reference to the page, add an error message to pCheck->zErrMsg.
                   3186: ** Return 1 if there are 2 ore more references to the page and 0 if
                   3187: ** if this is the first reference to the page.
                   3188: **
                   3189: ** Also check that the page number is in bounds.
                   3190: */
                   3191: static int checkRef(IntegrityCk *pCheck, int iPage, char *zContext){
                   3192:   if( iPage==0 ) return 1;
                   3193:   if( iPage>pCheck->nPage || iPage<0 ){
                   3194:     char zBuf[100];
                   3195:     sprintf(zBuf, "invalid page number %d", iPage);
                   3196:     checkAppendMsg(pCheck, zContext, zBuf);
                   3197:     return 1;
                   3198:   }
                   3199:   if( pCheck->anRef[iPage]==1 ){
                   3200:     char zBuf[100];
                   3201:     sprintf(zBuf, "2nd reference to page %d", iPage);
                   3202:     checkAppendMsg(pCheck, zContext, zBuf);
                   3203:     return 1;
                   3204:   }
                   3205:   return  (pCheck->anRef[iPage]++)>1;
                   3206: }
                   3207: 
                   3208: /*
                   3209: ** Check the integrity of the freelist or of an overflow page list.
                   3210: ** Verify that the number of pages on the list is N.
                   3211: */
                   3212: static void checkList(
                   3213:   IntegrityCk *pCheck,  /* Integrity checking context */
                   3214:   int isFreeList,       /* True for a freelist.  False for overflow page list */
                   3215:   int iPage,            /* Page number for first page in the list */
                   3216:   int N,                /* Expected number of pages in the list */
                   3217:   char *zContext        /* Context for error messages */
                   3218: ){
                   3219:   int i;
                   3220:   char zMsg[100];
                   3221:   while( N-- > 0 ){
                   3222:     OverflowPage *pOvfl;
                   3223:     if( iPage<1 ){
                   3224:       sprintf(zMsg, "%d pages missing from overflow list", N+1);
                   3225:       checkAppendMsg(pCheck, zContext, zMsg);
                   3226:       break;
                   3227:     }
                   3228:     if( checkRef(pCheck, iPage, zContext) ) break;
                   3229:     if( sqlitepager_get(pCheck->pPager, (Pgno)iPage, (void**)&pOvfl) ){
                   3230:       sprintf(zMsg, "failed to get page %d", iPage);
                   3231:       checkAppendMsg(pCheck, zContext, zMsg);
                   3232:       break;
                   3233:     }
                   3234:     if( isFreeList ){
                   3235:       FreelistInfo *pInfo = (FreelistInfo*)pOvfl->aPayload;
                   3236:       int n = SWAB32(pCheck->pBt, pInfo->nFree);
                   3237:       for(i=0; i<n; i++){
                   3238:         checkRef(pCheck, SWAB32(pCheck->pBt, pInfo->aFree[i]), zContext);
                   3239:       }
                   3240:       N -= n;
                   3241:     }
                   3242:     iPage = SWAB32(pCheck->pBt, pOvfl->iNext);
                   3243:     sqlitepager_unref(pOvfl);
                   3244:   }
                   3245: }
                   3246: 
                   3247: /*
                   3248: ** Return negative if zKey1<zKey2.
                   3249: ** Return zero if zKey1==zKey2.
                   3250: ** Return positive if zKey1>zKey2.
                   3251: */
                   3252: static int keyCompare(
                   3253:   const char *zKey1, int nKey1,
                   3254:   const char *zKey2, int nKey2
                   3255: ){
                   3256:   int min = nKey1>nKey2 ? nKey2 : nKey1;
                   3257:   int c = memcmp(zKey1, zKey2, min);
                   3258:   if( c==0 ){
                   3259:     c = nKey1 - nKey2;
                   3260:   }
                   3261:   return c;
                   3262: }
                   3263: 
                   3264: /*
                   3265: ** Do various sanity checks on a single page of a tree.  Return
                   3266: ** the tree depth.  Root pages return 0.  Parents of root pages
                   3267: ** return 1, and so forth.
                   3268: ** 
                   3269: ** These checks are done:
                   3270: **
                   3271: **      1.  Make sure that cells and freeblocks do not overlap
                   3272: **          but combine to completely cover the page.
                   3273: **      2.  Make sure cell keys are in order.
                   3274: **      3.  Make sure no key is less than or equal to zLowerBound.
                   3275: **      4.  Make sure no key is greater than or equal to zUpperBound.
                   3276: **      5.  Check the integrity of overflow pages.
                   3277: **      6.  Recursively call checkTreePage on all children.
                   3278: **      7.  Verify that the depth of all children is the same.
                   3279: **      8.  Make sure this page is at least 33% full or else it is
                   3280: **          the root of the tree.
                   3281: */
                   3282: static int checkTreePage(
                   3283:   IntegrityCk *pCheck,  /* Context for the sanity check */
                   3284:   int iPage,            /* Page number of the page to check */
                   3285:   MemPage *pParent,     /* Parent page */
                   3286:   char *zParentContext, /* Parent context */
                   3287:   char *zLowerBound,    /* All keys should be greater than this, if not NULL */
                   3288:   int nLower,           /* Number of characters in zLowerBound */
                   3289:   char *zUpperBound,    /* All keys should be less than this, if not NULL */
                   3290:   int nUpper            /* Number of characters in zUpperBound */
                   3291: ){
                   3292:   MemPage *pPage;
                   3293:   int i, rc, depth, d2, pgno;
                   3294:   char *zKey1, *zKey2;
                   3295:   int nKey1, nKey2;
                   3296:   BtCursor cur;
                   3297:   Btree *pBt;
                   3298:   char zMsg[100];
                   3299:   char zContext[100];
                   3300:   char hit[SQLITE_USABLE_SIZE];
                   3301: 
                   3302:   /* Check that the page exists
                   3303:   */
                   3304:   cur.pBt = pBt = pCheck->pBt;
                   3305:   if( iPage==0 ) return 0;
                   3306:   if( checkRef(pCheck, iPage, zParentContext) ) return 0;
                   3307:   sprintf(zContext, "On tree page %d: ", iPage);
                   3308:   if( (rc = sqlitepager_get(pCheck->pPager, (Pgno)iPage, (void**)&pPage))!=0 ){
                   3309:     sprintf(zMsg, "unable to get the page. error code=%d", rc);
                   3310:     checkAppendMsg(pCheck, zContext, zMsg);
                   3311:     return 0;
                   3312:   }
                   3313:   if( (rc = initPage(pBt, pPage, (Pgno)iPage, pParent))!=0 ){
                   3314:     sprintf(zMsg, "initPage() returns error code %d", rc);
                   3315:     checkAppendMsg(pCheck, zContext, zMsg);
                   3316:     sqlitepager_unref(pPage);
                   3317:     return 0;
                   3318:   }
                   3319: 
                   3320:   /* Check out all the cells.
                   3321:   */
                   3322:   depth = 0;
                   3323:   if( zLowerBound ){
                   3324:     zKey1 = sqliteMalloc( nLower+1 );
                   3325:     memcpy(zKey1, zLowerBound, nLower);
                   3326:     zKey1[nLower] = 0;
                   3327:   }else{
                   3328:     zKey1 = 0;
                   3329:   }
                   3330:   nKey1 = nLower;
                   3331:   cur.pPage = pPage;
                   3332:   for(i=0; i<pPage->nCell; i++){
                   3333:     Cell *pCell = pPage->apCell[i];
                   3334:     int sz;
                   3335: 
                   3336:     /* Check payload overflow pages
                   3337:     */
                   3338:     nKey2 = NKEY(pBt, pCell->h);
                   3339:     sz = nKey2 + NDATA(pBt, pCell->h);
                   3340:     sprintf(zContext, "On page %d cell %d: ", iPage, i);
                   3341:     if( sz>MX_LOCAL_PAYLOAD ){
                   3342:       int nPage = (sz - MX_LOCAL_PAYLOAD + OVERFLOW_SIZE - 1)/OVERFLOW_SIZE;
                   3343:       checkList(pCheck, 0, SWAB32(pBt, pCell->ovfl), nPage, zContext);
                   3344:     }
                   3345: 
                   3346:     /* Check that keys are in the right order
                   3347:     */
                   3348:     cur.idx = i;
                   3349:     zKey2 = sqliteMallocRaw( nKey2+1 );
                   3350:     getPayload(&cur, 0, nKey2, zKey2);
                   3351:     if( zKey1 && keyCompare(zKey1, nKey1, zKey2, nKey2)>=0 ){
                   3352:       checkAppendMsg(pCheck, zContext, "Key is out of order");
                   3353:     }
                   3354: 
                   3355:     /* Check sanity of left child page.
                   3356:     */
                   3357:     pgno = SWAB32(pBt, pCell->h.leftChild);
                   3358:     d2 = checkTreePage(pCheck, pgno, pPage, zContext, zKey1,nKey1,zKey2,nKey2);
                   3359:     if( i>0 && d2!=depth ){
                   3360:       checkAppendMsg(pCheck, zContext, "Child page depth differs");
                   3361:     }
                   3362:     depth = d2;
                   3363:     sqliteFree(zKey1);
                   3364:     zKey1 = zKey2;
                   3365:     nKey1 = nKey2;
                   3366:   }
                   3367:   pgno = SWAB32(pBt, pPage->u.hdr.rightChild);
                   3368:   sprintf(zContext, "On page %d at right child: ", iPage);
                   3369:   checkTreePage(pCheck, pgno, pPage, zContext, zKey1,nKey1,zUpperBound,nUpper);
                   3370:   sqliteFree(zKey1);
                   3371:  
                   3372:   /* Check for complete coverage of the page
                   3373:   */
                   3374:   memset(hit, 0, sizeof(hit));
                   3375:   memset(hit, 1, sizeof(PageHdr));
                   3376:   for(i=SWAB16(pBt, pPage->u.hdr.firstCell); i>0 && i<SQLITE_USABLE_SIZE; ){
                   3377:     Cell *pCell = (Cell*)&pPage->u.aDisk[i];
                   3378:     int j;
                   3379:     for(j=i+cellSize(pBt, pCell)-1; j>=i; j--) hit[j]++;
                   3380:     i = SWAB16(pBt, pCell->h.iNext);
                   3381:   }
                   3382:   for(i=SWAB16(pBt,pPage->u.hdr.firstFree); i>0 && i<SQLITE_USABLE_SIZE; ){
                   3383:     FreeBlk *pFBlk = (FreeBlk*)&pPage->u.aDisk[i];
                   3384:     int j;
                   3385:     for(j=i+SWAB16(pBt,pFBlk->iSize)-1; j>=i; j--) hit[j]++;
                   3386:     i = SWAB16(pBt,pFBlk->iNext);
                   3387:   }
                   3388:   for(i=0; i<SQLITE_USABLE_SIZE; i++){
                   3389:     if( hit[i]==0 ){
                   3390:       sprintf(zMsg, "Unused space at byte %d of page %d", i, iPage);
                   3391:       checkAppendMsg(pCheck, zMsg, 0);
                   3392:       break;
                   3393:     }else if( hit[i]>1 ){
                   3394:       sprintf(zMsg, "Multiple uses for byte %d of page %d", i, iPage);
                   3395:       checkAppendMsg(pCheck, zMsg, 0);
                   3396:       break;
                   3397:     }
                   3398:   }
                   3399: 
                   3400:   /* Check that free space is kept to a minimum
                   3401:   */
                   3402: #if 0
                   3403:   if( pParent && pParent->nCell>2 && pPage->nFree>3*SQLITE_USABLE_SIZE/4 ){
                   3404:     sprintf(zMsg, "free space (%d) greater than max (%d)", pPage->nFree,
                   3405:        SQLITE_USABLE_SIZE/3);
                   3406:     checkAppendMsg(pCheck, zContext, zMsg);
                   3407:   }
                   3408: #endif
                   3409: 
                   3410:   sqlitepager_unref(pPage);
                   3411:   return depth;
                   3412: }
                   3413: 
                   3414: /*
                   3415: ** This routine does a complete check of the given BTree file.  aRoot[] is
                   3416: ** an array of pages numbers were each page number is the root page of
                   3417: ** a table.  nRoot is the number of entries in aRoot.
                   3418: **
                   3419: ** If everything checks out, this routine returns NULL.  If something is
                   3420: ** amiss, an error message is written into memory obtained from malloc()
                   3421: ** and a pointer to that error message is returned.  The calling function
                   3422: ** is responsible for freeing the error message when it is done.
                   3423: */
                   3424: char *fileBtreeIntegrityCheck(Btree *pBt, int *aRoot, int nRoot){
                   3425:   int i;
                   3426:   int nRef;
                   3427:   IntegrityCk sCheck;
                   3428: 
                   3429:   nRef = *sqlitepager_stats(pBt->pPager);
                   3430:   if( lockBtree(pBt)!=SQLITE_OK ){
                   3431:     return sqliteStrDup("Unable to acquire a read lock on the database");
                   3432:   }
                   3433:   sCheck.pBt = pBt;
                   3434:   sCheck.pPager = pBt->pPager;
                   3435:   sCheck.nPage = sqlitepager_pagecount(sCheck.pPager);
                   3436:   if( sCheck.nPage==0 ){
                   3437:     unlockBtreeIfUnused(pBt);
                   3438:     return 0;
                   3439:   }
                   3440:   sCheck.anRef = sqliteMallocRaw( (sCheck.nPage+1)*sizeof(sCheck.anRef[0]) );
                   3441:   sCheck.anRef[1] = 1;
                   3442:   for(i=2; i<=sCheck.nPage; i++){ sCheck.anRef[i] = 0; }
                   3443:   sCheck.zErrMsg = 0;
                   3444: 
                   3445:   /* Check the integrity of the freelist
                   3446:   */
                   3447:   checkList(&sCheck, 1, SWAB32(pBt, pBt->page1->freeList),
                   3448:             SWAB32(pBt, pBt->page1->nFree), "Main freelist: ");
                   3449: 
                   3450:   /* Check all the tables.
                   3451:   */
                   3452:   for(i=0; i<nRoot; i++){
                   3453:     if( aRoot[i]==0 ) continue;
                   3454:     checkTreePage(&sCheck, aRoot[i], 0, "List of tree roots: ", 0,0,0,0);
                   3455:   }
                   3456: 
                   3457:   /* Make sure every page in the file is referenced
                   3458:   */
                   3459:   for(i=1; i<=sCheck.nPage; i++){
                   3460:     if( sCheck.anRef[i]==0 ){
                   3461:       char zBuf[100];
                   3462:       sprintf(zBuf, "Page %d is never used", i);
                   3463:       checkAppendMsg(&sCheck, zBuf, 0);
                   3464:     }
                   3465:   }
                   3466: 
                   3467:   /* Make sure this analysis did not leave any unref() pages
                   3468:   */
                   3469:   unlockBtreeIfUnused(pBt);
                   3470:   if( nRef != *sqlitepager_stats(pBt->pPager) ){
                   3471:     char zBuf[100];
                   3472:     sprintf(zBuf, 
                   3473:       "Outstanding page count goes from %d to %d during this analysis",
                   3474:       nRef, *sqlitepager_stats(pBt->pPager)
                   3475:     );
                   3476:     checkAppendMsg(&sCheck, zBuf, 0);
                   3477:   }
                   3478: 
                   3479:   /* Clean  up and report errors.
                   3480:   */
                   3481:   sqliteFree(sCheck.anRef);
                   3482:   return sCheck.zErrMsg;
                   3483: }
                   3484: 
                   3485: /*
                   3486: ** Return the full pathname of the underlying database file.
                   3487: */
                   3488: static const char *fileBtreeGetFilename(Btree *pBt){
                   3489:   assert( pBt->pPager!=0 );
                   3490:   return sqlitepager_filename(pBt->pPager);
                   3491: }
                   3492: 
                   3493: /*
                   3494: ** Copy the complete content of pBtFrom into pBtTo.  A transaction
                   3495: ** must be active for both files.
                   3496: **
                   3497: ** The size of file pBtFrom may be reduced by this operation.
                   3498: ** If anything goes wrong, the transaction on pBtFrom is rolled back.
                   3499: */
                   3500: static int fileBtreeCopyFile(Btree *pBtTo, Btree *pBtFrom){
                   3501:   int rc = SQLITE_OK;
                   3502:   Pgno i, nPage, nToPage;
                   3503: 
                   3504:   if( !pBtTo->inTrans || !pBtFrom->inTrans ) return SQLITE_ERROR;
                   3505:   if( pBtTo->needSwab!=pBtFrom->needSwab ) return SQLITE_ERROR;
                   3506:   if( pBtTo->pCursor ) return SQLITE_BUSY;
                   3507:   memcpy(pBtTo->page1, pBtFrom->page1, SQLITE_USABLE_SIZE);
                   3508:   rc = sqlitepager_overwrite(pBtTo->pPager, 1, pBtFrom->page1);
                   3509:   nToPage = sqlitepager_pagecount(pBtTo->pPager);
                   3510:   nPage = sqlitepager_pagecount(pBtFrom->pPager);
                   3511:   for(i=2; rc==SQLITE_OK && i<=nPage; i++){
                   3512:     void *pPage;
                   3513:     rc = sqlitepager_get(pBtFrom->pPager, i, &pPage);
                   3514:     if( rc ) break;
                   3515:     rc = sqlitepager_overwrite(pBtTo->pPager, i, pPage);
                   3516:     if( rc ) break;
                   3517:     sqlitepager_unref(pPage);
                   3518:   }
                   3519:   for(i=nPage+1; rc==SQLITE_OK && i<=nToPage; i++){
                   3520:     void *pPage;
                   3521:     rc = sqlitepager_get(pBtTo->pPager, i, &pPage);
                   3522:     if( rc ) break;
                   3523:     rc = sqlitepager_write(pPage);
                   3524:     sqlitepager_unref(pPage);
                   3525:     sqlitepager_dont_write(pBtTo->pPager, i);
                   3526:   }
                   3527:   if( !rc && nPage<nToPage ){
                   3528:     rc = sqlitepager_truncate(pBtTo->pPager, nPage);
                   3529:   }
                   3530:   if( rc ){
                   3531:     fileBtreeRollback(pBtTo);
                   3532:   }
                   3533:   return rc;  
                   3534: }
                   3535: 
                   3536: /*
                   3537: ** The following tables contain pointers to all of the interface
                   3538: ** routines for this implementation of the B*Tree backend.  To
                   3539: ** substitute a different implemention of the backend, one has merely
                   3540: ** to provide pointers to alternative functions in similar tables.
                   3541: */
                   3542: static BtOps sqliteBtreeOps = {
                   3543:     fileBtreeClose,
                   3544:     fileBtreeSetCacheSize,
                   3545:     fileBtreeSetSafetyLevel,
                   3546:     fileBtreeBeginTrans,
                   3547:     fileBtreeCommit,
                   3548:     fileBtreeRollback,
                   3549:     fileBtreeBeginCkpt,
                   3550:     fileBtreeCommitCkpt,
                   3551:     fileBtreeRollbackCkpt,
                   3552:     fileBtreeCreateTable,
                   3553:     fileBtreeCreateTable,  /* Really sqliteBtreeCreateIndex() */
                   3554:     fileBtreeDropTable,
                   3555:     fileBtreeClearTable,
                   3556:     fileBtreeCursor,
                   3557:     fileBtreeGetMeta,
                   3558:     fileBtreeUpdateMeta,
                   3559:     fileBtreeIntegrityCheck,
                   3560:     fileBtreeGetFilename,
                   3561:     fileBtreeCopyFile,
                   3562:     fileBtreePager,
                   3563: #ifdef SQLITE_TEST
                   3564:     fileBtreePageDump,
                   3565: #endif
                   3566: };
                   3567: static BtCursorOps sqliteBtreeCursorOps = {
                   3568:     fileBtreeMoveto,
                   3569:     fileBtreeDelete,
                   3570:     fileBtreeInsert,
                   3571:     fileBtreeFirst,
                   3572:     fileBtreeLast,
                   3573:     fileBtreeNext,
                   3574:     fileBtreePrevious,
                   3575:     fileBtreeKeySize,
                   3576:     fileBtreeKey,
                   3577:     fileBtreeKeyCompare,
                   3578:     fileBtreeDataSize,
                   3579:     fileBtreeData,
                   3580:     fileBtreeCloseCursor,
                   3581: #ifdef SQLITE_TEST
                   3582:     fileBtreeCursorDump,
                   3583: #endif
                   3584: };

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>