monotone

monotone Mtn Source Tree

Root/sqlite/btree.c

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

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status