Annotation of embedaddon/php/ext/sqlite/libsqlite/src/btree.c, revision 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, ¬Used);
! 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>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to btree.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / php / ext / sqlite / libsqlite / src