Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Continued work on btree (CVS 219) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
18500cdcc1a42118cdf650681ebb1cbe |
User & Date: | drh 2001-05-24 21:06:35.000 |
Context
2001-05-26
| ||
13:15 | :-) (CVS 220) (check-in: 45a0e0fc8c user: drh tags: trunk) | |
2001-05-24
| ||
21:06 | Continued work on btree (CVS 219) (check-in: 18500cdcc1 user: drh tags: trunk) | |
2001-05-21
| ||
13:45 | :-) (CVS 218) (check-in: 523d52dfa6 user: drh tags: trunk) | |
Changes
Changes to src/btree.c.
︙ | ︙ | |||
17 18 19 20 21 22 23 | ** Boston, MA 02111-1307, USA. ** ** Author contact information: ** drh@hwaci.com ** http://www.hwaci.com/drh/ ** ************************************************************************* | | | 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | ** Boston, MA 02111-1307, USA. ** ** Author contact information: ** drh@hwaci.com ** http://www.hwaci.com/drh/ ** ************************************************************************* ** $Id: btree.c,v 1.7 2001/05/24 21:06:35 drh Exp $ */ #include "sqliteInt.h" #include "pager.h" #include "btree.h" #include <assert.h> /* |
︙ | ︙ | |||
93 94 95 96 97 98 99 | }; #define MAGIC_1 0x7264dc61 #define MAGIC_2 0x54e55d9e /* ** Each database page has a header as follows: ** | | | 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 | }; #define MAGIC_1 0x7264dc61 #define MAGIC_2 0x54e55d9e /* ** Each database page has a header as follows: ** ** page1_header Optional instance of Page1Header structure ** rightmost_pgno Page number of the right-most child page ** first_cell Index into MemPage.aPage of first cell ** first_free Index of first free block ** ** MemPage.pStart always points to the rightmost_pgno. First_free is ** 0 if there is no free space on this page. Otherwise, first_free is ** the index in MemPage.aPage[] of a FreeBlk structure that describes |
︙ | ︙ | |||
134 135 136 137 138 139 140 | u32 nData; /* Number of bytes of data */ char aData[4]; /* Key and data */ }; /* ** Free space on a page is remembered using a linked list of the FreeBlk ** structures. Space on a database page is allocated in increments of | | > | | | > > > > > < | | 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 | u32 nData; /* Number of bytes of data */ char aData[4]; /* Key and data */ }; /* ** Free space on a page is remembered using a linked list of the FreeBlk ** structures. Space on a database page is allocated in increments of ** at least 4 bytes and is always aligned to a 4-byte boundry. The ** linked list of freeblocks is always kept in order by address. */ struct FreeBlk { u16 iSize; /* Number of bytes in this block of free space */ u16 iNext; /* Index in MemPage.aPage[] of the next free block */ }; /* ** When the key and data for a single entry in the BTree will not fit in ** the MX_LOACAL_PAYLOAD bytes of space available on the database page, ** then all extra data is written to a linked list of overflow pages. ** Each overflow page is an instance of the following structure. ** ** Unused pages in the database are also represented by instances of ** the OverflowPage structure. The Page1Header.freeList field is the ** page number of the first page in a linked list of unused database ** pages. */ struct OverflowPage { Pgno next; char aData[OVERFLOW_SIZE]; }; /* ** For every page in the database file, an instance of the following structure ** is stored in memory. The aPage[] array contains the data obtained from ** the disk. The rest is auxiliary data that held in memory only. The ** auxiliary data is only valid for regular database pages - the auxiliary ** data is meaningless for overflow pages and pages on the freelist. ** ** Of particular interest in the auxiliary data is the aCell[] entry. Each ** aCell[] entry is a pointer to a Cell structure in aPage[]. The cells are ** put in this array so that they can be accessed in constant time, rather ** than in linear time which would be needed if we walked the linked list. ** ** The pParent field points back to the parent page. This allows us to ** walk up the BTree from any leaf to the root. Care must be taken to ** unref() the parent page pointer when this page is no longer referenced. ** The pageDestructor() routine handles that. */ struct MemPage { char aPage[SQLITE_PAGE_SIZE]; /* Page data stored on disk */ unsigned char isInit; /* True if auxiliary data is initialized */ unsigned char validLeft; /* True if MemPage.left is valid */ unsigned char validRight; /* True if MemPage.right is valid */ MemPage *pParent; /* The parent of this page. NULL for root */ Pgno left; /* Left sibling page. 0==none */ Pgno right; /* Right sibling page. 0==none */ int idxStart; /* Index in aPage[] of real data */ PageHdr *pStart; /* Points to aPage[idxStart] */ int nFree; /* Number of free bytes in aPage[] */ int nCell; /* Number of entries on this page */ Cell *aCell[MX_CELL]; /* All data entires in sorted order */ |
︙ | ︙ | |||
201 202 203 204 205 206 207 | typedef Btree Bt; /* ** A cursor is a pointer to a particular entry in the BTree. ** The entry is identified by its MemPage and the index in ** MemPage.aCell[] of the entry. */ | | | | | | | | > | < | 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 | typedef Btree Bt; /* ** A cursor is a pointer to a particular entry in the BTree. ** The entry is identified by its MemPage and the index in ** MemPage.aCell[] of the entry. */ struct BtCursor { Btree *pBt; /* The pointer back to the BTree */ BtCursor *pPrev, *pNext; /* List of all cursors */ MemPage *pPage; /* Page that contains the entry */ int idx; /* Index of the entry in pPage->aCell[] */ int skip_incr; /* */ }; /* ** Defragment the page given. All Cells are moved to the ** beginning of the page and all free space is collected ** into one big FreeBlk at the end of the page. */ static void defragmentPage(MemPage *pPage){ int pc; int i, n; FreeBlk *pFBlk; char newPage[SQLITE_PAGE_SIZE]; |
︙ | ︙ | |||
234 235 236 237 238 239 240 | n = ROUNDUP(n); n += sizeof(Cell) - sizeof(pCell->aData); pCell->iNext = i<pPage->nCell ? pc + n : 0; memcpy(&newPage[pc], pCell, n); pPage->aCell[i] = (Cell*)&pPage->aPage[pc]; pc += n; } | | > > | | > < | > > > > | 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 | n = ROUNDUP(n); n += sizeof(Cell) - sizeof(pCell->aData); pCell->iNext = i<pPage->nCell ? pc + n : 0; memcpy(&newPage[pc], pCell, n); pPage->aCell[i] = (Cell*)&pPage->aPage[pc]; pc += n; } assert( pPage->nFree==SQLITE_PAGE_SIZE-pc ); memcpy(pPage->aPage, newPage, pc); pFBlk = &pPage->aPage[pc]; pFBlk->iSize = SQLITE_PAGE_SIZE - pc; pFBlk->iNext = 0; pPage->pStart->firstFree = pc; memset(&pFBlk[1], 0, SQLITE_PAGE_SIZE - pc - sizeof(FreeBlk)); } /* ** Allocate space on a page. The space needs to be at least ** nByte bytes in size. (Actually, all allocations are rounded ** up to the next even multiple of 4.) Return the index into ** pPage->aPage[] of the first byte of the new allocation. ** Or return 0 if there is not enough free space on the page to ** satisfy the allocation request. ** ** If the page contains nBytes of free space but does not contain ** nBytes of contiguous free space, then defragementPage() is ** called to consolidate all free space before allocating the ** new chunk. */ static int allocSpace(MemPage *pPage, int nByte){ FreeBlk *p; u16 *pIdx; int start; nByte = ROUNDUP(nByte); if( pPage->nFree<nByte ) return 0; pIdx = &pPage->pStart->firstFree; p = (FreeBlk*)&pPage->aPage[*pIdx]; while( p->iSize<nByte ){ if( p->iNext==0 ){ defragmentPage(pPage); pIdx = &pPage->pStart->firstFree; }else{ pIdx = &p->iNext; } p = (FreeBlk*)&pPage->aPage[*pIdx]; } if( p->iSize==nByte ){ start = *pIdx; *pIdx = p->iNext; }else{ start = *pIdx; FreeBlk *pNew = (FreeBlk*)&pPage->aPage[start + nByte]; pNew->iNext = p->iNext; pNew->iSize = p->iSize - nByte; *pIdx = start + nByte; } pPage->nFree -= nByte; return start; } /* ** Return a section of the MemPage.aPage[] to the freelist. |
︙ | ︙ | |||
331 332 333 334 335 336 337 338 | } *pIdx = start; pPage->nFree += size; } /* ** Initialize the auxiliary information for a disk block. */ | > > > > > > | | | > | 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 | } *pIdx = start; pPage->nFree += size; } /* ** Initialize the auxiliary information for a disk block. ** ** Return SQLITE_OK on success. If we see that the page does ** not contained a well-formed database page, then return ** SQLITE_CORRUPT. Note that a return of SQLITE_OK does not ** guarantee that the page is well-formed. It only shows that ** we failed to detect any corruption. */ static int initPage(MemPage *pPage, Pgno pgnoThis, MemPage *pParent){ int idx; Cell *pCell; FreeBlk *pFBlk; pPage->idxStart = (pgnoThis==1) ? sizeof(Page1Header) : 0; pPage->pStart = (PageHdr*)&pPage->aPage[pPage->idxStart]; pPage->isInit = 1; assert( pPage->pParent==0 ); pPage->pParent = pParent; if( pParent ) sqlitepager_ref(pParent); pPage->nCell = 0; idx = pPage->pStart->firstCell; while( idx!=0 ){ if( idx>SQLITE_PAGE_SIZE-sizeof(Cell) ) goto page_format_error; if( idx<pPage->idxStart + sizeof(PageHeader) ) goto page_format_error; pCell = (Cell*)&pPage->aPage[idx]; pPage->aCell[pPage->nCell++] = pCell; |
︙ | ︙ | |||
366 367 368 369 370 371 372 373 374 375 376 377 | idx = pFBlk->iNext; } return SQLITE_OK; page_format_error: return SQLITE_CORRUPT; } /* ** Open a new database. ** ** Actually, this routine just sets up the internal data structures | > > > > > > > > > > > > > > | | > | 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 | idx = pFBlk->iNext; } return SQLITE_OK; page_format_error: return SQLITE_CORRUPT; } /* ** This routine is called when the reference count for a page ** reaches zero. We need to unref the pParent pointer when that ** happens. */ static void pageDestructor(void *pData){ MemPage *pPage = (MemPage*)pData; if( pPage->pParent ){ MemPage *pParent = pPage->pParent; pPage->pParent = 0; sqlitepager_unref(pParent); } } /* ** Open a new database. ** ** Actually, this routine just sets up the internal data structures ** for accessing the database. We do not open the database file ** until the first page is loaded. */ int sqliteBtreeOpen(const char *zFilename, int mode, Btree **ppBtree){ Btree *pBt; pBt = sqliteMalloc( sizeof(*pBt) ); if( pBt==0 ){ **ppBtree = 0; return SQLITE_NOMEM; } rc = sqlitepager_open(&pBt->pPager, zFilename, 100, EXTRA_SPACE); if( rc!=SQLITE_OK ){ if( pBt->pPager ) sqlitepager_close(pBt->pPager); sqliteFree(pBt); *ppBtree = 0; return rc; } sqlitepager_set_destructor(pBt->pPager, pageDestructor); pBt->pCursor = 0; pBt->page1 = 0; *ppBtree = pBt; return SQLITE_OK; } /* |
︙ | ︙ | |||
423 424 425 426 427 428 429 | */ static int lockBtree(Btree *pBt){ int rc; if( pBt->page1 ) return SQLITE_OK; rc = sqlitepager_get(pBt->pPager, 1, &pBt->page1); if( rc!=SQLITE_OK ) return rc; rc = initPage(pBt->page1, 1, 0); | | | | > | > > > > > > | 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 | */ static int lockBtree(Btree *pBt){ int rc; if( pBt->page1 ) return SQLITE_OK; rc = sqlitepager_get(pBt->pPager, 1, &pBt->page1); if( rc!=SQLITE_OK ) return rc; rc = initPage(pBt->page1, 1, 0); if( rc!=SQLITE_OK ) goto page1_init_failed; /* Do some checking to help insure the file we opened really is ** a valid database file. */ if( sqlitepager_pagecount(pBt->pPager)>0 ){ Page1Header *pP1 = (Page1Header*)pBt->page1; if( pP1->magic1!=MAGIC_1 || pP1->magic2!=MAGIC_2 ){ rc = SQLITE_CORRUPT; goto page1_init_failed; } } return rc; page1_init_failed: sqlitepager_unref(pBt->page1); pBt->page1 = 0; return rc; } /* ** Attempt to start a new transaction. */ int sqliteBtreeBeginTrans(Btree *pBt){ int rc; Page1Header *pP1; if( pBt->inTrans ) return SQLITE_ERROR; if( pBt->page1==0 ){ rc = lockBtree(pBt); if( rc!=SQLITE_OK ) return rc; } rc = sqlitepager_write(pBt->page1); if( rc==SQLITE_OK ){ pBt->inTrans = 1; } pP1 = (Page1Header*)pBt->page1; if( pP1->magic1==0 ){ pP1->magic1 = MAGIC_1; pP1->magic2 = MAGIC_2; } return rc; } /* ** Remove the last reference to the database file. This will ** remove the read lock. |
︙ | ︙ | |||
477 478 479 480 481 482 483 | /* ** Commit the transaction currently in progress. All cursors ** must be closed before this routine is called. */ int sqliteBtreeCommit(Btree *pBt){ int rc; | | | | 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 | /* ** Commit the transaction currently in progress. All cursors ** must be closed before this routine is called. */ int sqliteBtreeCommit(Btree *pBt){ int rc; if( pBt->pCursor!=0 ) return SQLITE_ERROR; rc = sqlitepager_commit(pBt->pPager); unlockBtree(pBt); return rc; } /* ** Rollback the transaction in progress. All cursors must be ** closed before this routine is called. */ int sqliteBtreeRollback(Btree *pBt){ int rc; if( pBt->pCursor!=0 ) return SQLITE_ERROR; rc = sqlitepager_rollback(pBt->pPager); unlockBtree(pBt); return rc; } /* ** Create a new cursor. The act of acquiring a cursor |
︙ | ︙ | |||
529 530 531 532 533 534 535 | rc = sqlitepager_get(pBt->pPager, 1, &pCur->pPage); if( rc!=SQLITE_OK ){ sqliteFree(pCur); *ppCur = 0; return rc; } if( !pCur->pPage->isInit ){ | | > > | 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 | rc = sqlitepager_get(pBt->pPager, 1, &pCur->pPage); if( rc!=SQLITE_OK ){ sqliteFree(pCur); *ppCur = 0; return rc; } if( !pCur->pPage->isInit ){ initPage(pCur->pPage, 1, 0); } pCur->idx = 0; pCur->depth = 0; pCur->aPage[0] = pCur->pPage; *ppCur = pCur; return SQLITE_OK; } /* ** Close a cursor. */ |
︙ | ︙ | |||
558 559 560 561 562 563 564 | if( pBt->pCursor==0 && pBt->inTrans==0 ){ unlockBtree(pBt); } sqliteFree(pCur); } /* | | | | | > | > > | | | > | > > > > > > > > > > > | 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 | if( pBt->pCursor==0 && pBt->inTrans==0 ){ unlockBtree(pBt); } sqliteFree(pCur); } /* ** Write the number of bytes of key for the entry the cursor is ** pointing to into *pSize. Return SQLITE_OK. Failure is not ** possible. */ int sqliteBtreeKeySize(BtCursor *pCur, int *pSize){ Cell *pCell; MemPage *pPage; pPage = pCur->pPage; assert( pPage!=0 ); if( pCur->idx >= pPage->nCell ){ *pSize = 0; }else{ pCell = pPage->aCell[pCur->idx]; *psize = pCell->nKey; } return SQLITE_OK; } /* ** Read payload information from the entry that the pCur cursor is ** pointing to. Begin reading the payload at "offset" and read ** a total of "amt" bytes. Put the result in zBuf. ** ** This routine does not make a distinction between key and data. ** It just reads bytes from the payload area. */ static int getPayload(BtCursor *pCur, int offset, int amt, char *zBuf){ char *aData; Pgno nextPage; assert( pCur!=0 && pCur->pPage!=0 ); assert( pCur->idx>=0 && pCur->idx<pCur->nCell ); aData = pCur->pPage->aCell[pCur->idx].aData; if( offset<MX_LOCAL_PAYLOAD ){ int a = amt; if( a+offset>MX_LOCAL_PAYLOAD ){ a = MX_LOCAL_PAYLOAD - offset; } memcpy(zBuf, &aData[offset], a); |
︙ | ︙ | |||
615 616 617 618 619 620 621 | zBuf += a; } sqlitepager_unref(pOvfl); } return amt==0 ? SQLITE_OK : SQLITE_CORRUPT; } | > > > > > > > | > > > > > > > > > > > > > > > > > > > > > | > > > > > > > > > > > > > > > > > > > > > | > > > > > > > > > > > > > > | 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 | zBuf += a; } sqlitepager_unref(pOvfl); } return amt==0 ? SQLITE_OK : SQLITE_CORRUPT; } /* ** Read part of the key associated with cursor pCur. A total ** of "amt" bytes will be transfered into zBuf[]. The transfer ** begins at "offset". If the key does not contain enough data ** to satisfy the request, no data is fetched and this routine ** returns SQLITE_ERROR. */ int sqliteBtreeKey(BtCursor *pCur, int offset, int amt, char *zBuf){ Cell *pCell; MemPage *pPage; if( amt<0 ) return SQLITE_ERROR; if( offset<0 ) return SQLITE_ERROR; if( amt==0 ) return SQLITE_OK; pPage = pCur->pPage; assert( pPage!=0 ); if( pCur->idx >= pPage->nCell ){ return SQLITE_ERROR; } pCell = pPage->aCell[pCur->idx]; if( amt+offset > pCell->nKey ){ return getPayload(pCur, offset, amt, zBuf); } /* ** Write the number of bytes of data on the entry that the cursor ** is pointing to into *pSize. Return SQLITE_OK. Failure is ** not possible. */ int sqliteBtreeDataSize(BtCursor *pCur, int *pSize){ Cell *pCell; MemPage *pPage; pPage = pCur->pPage; assert( pPage!=0 ); if( pCur->idx >= pPage->nCell ){ *pSize = 0; }else{ pCell = pPage->aCell[pCur->idx]; *pSize = pCell->nData; } return SQLITE_OK; } /* ** Read part of the data associated with cursor pCur. A total ** of "amt" bytes will be transfered into zBuf[]. The transfer ** begins at "offset". If the size of the data in the record ** is insufficent to satisfy this request then no data is read ** and this routine returns SQLITE_ERROR. */ int sqliteBtreeData(BtCursor *pCur, int offset, int amt, char *zBuf){ Cell *pCell; MemPage *pPage; if( amt<0 ) return SQLITE_ERROR; if( offset<0 ) return SQLITE_ERROR; if( amt==0 ) return SQLITE_OK; pPage = pCur->pPage; assert( pPage!=0 ); if( pCur->idx >= pPage->nCell ){ return SQLITE_ERROR; } pCell = pPage->aCell[pCur->idx]; if( amt+offset > pCell->nKey ){ return getPayload(pCur, offset + pCell->nKey, amt, zBuf); } /* ** Compare the key for the entry that pCur points to against the ** given key (pKey,nKeyOrig). Put the comparison result in *pResult. ** The result is negative if pCur<pKey, zero if they are equal and ** positive if pCur>pKey. ** |
︙ | ︙ | |||
661 662 663 664 665 666 667 | nextPage = *(Pgno*)&pCell->aData[MX_LOCAL_PAYLOAD]; while( nKey>0 ){ OverflowPage *pOvfl; if( nextPage==0 ){ return SQLITE_CORRUPT; } rc = sqlitepager_get(pCur->pBt->pPager, nextPage, &pOvfl); | | | 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 | nextPage = *(Pgno*)&pCell->aData[MX_LOCAL_PAYLOAD]; while( nKey>0 ){ OverflowPage *pOvfl; if( nextPage==0 ){ return SQLITE_CORRUPT; } rc = sqlitepager_get(pCur->pBt->pPager, nextPage, &pOvfl); if( rc ){ return rc; } nextPage = pOvfl->next; n = nKey; if( n>OVERFLOW_SIZE ){ n = OVERFLOW_SIZE; } |
︙ | ︙ | |||
683 684 685 686 687 688 689 690 691 | pKey += n; } c = pCell->nKey - nKeyOrig; *pResult = c; return SQLITE_OK; } /* Move the cursor so that it points to an entry near pKey. | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | > | > | > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | | 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 | pKey += n; } c = pCell->nKey - nKeyOrig; *pResult = c; return SQLITE_OK; } /* ** Move the cursor down to a new child page. */ static int childPage(BtCursor *pCur, int newPgno){ int rc; MemPage *pNewPage; rc = sqlitepager_get(pCur->pBt->pPager, newPgno, &pNewPage); if( rc ){ return rc; } if( !pNewPage->isInit ){ initPage(pNewPage, newPgno, pCur->pPage); } sqlitepager_unref(pCur->pPage); pCur->pPage = pNewPage; pCur->idx = 0; return SQLITE_OK; } /* ** Move the cursor up to the parent page */ static int parentPage(BtCursor *pCur){ Pgno oldPgno; MemPage *pParent; pParent = pCur->pPage->pParent; oldPgno = sqlitepager_pagenumber(pCur->pPage); if( pParent==0 ){ return SQLITE_INTERNAL; } sqlitepager_ref(pParent); sqlitepager_unref(pCur->pPage); pCur->pPage = pParent; pCur->idx = pPage->nCell; for(i=0; i<pPage->nCell; i++){ if( pPage->aCell[i].pgno==oldPgno ){ pCur->idx = i; break; } } } /* ** Move the cursor to the root page */ static int rootPage(BtCursor *pCur){ MemPage *pNew; pNew = pCur->pBt->page1; sqlitepager_ref(pNew); sqlitepager_unref(pCur->pPage); pCur->pPage = pNew; pCur->idx = 0; return SQLITE_OK; } /* Move the cursor so that it points to an entry near pKey. ** Return a success code. ** ** If pRes!=NULL, then *pRes is written with an integer code to ** describe the results. *pRes is set to 0 if the cursor is left ** pointing at an entry that exactly matches pKey. *pRes is made ** negative if the cursor is on the largest entry less than pKey. ** *pRes is set positive if the cursor is on the smallest entry ** greater than pKey. *pRes is not changed if the return value ** is something other than SQLITE_OK; */ int sqliteBtreeMoveto(BtCursor *pCur, void *pKey, int nKey, int *pRes){ int rc; rc = rootPage(pCur); if( rc ) return rc; for(;;){ int lwr, upr; Pgno chldPg; MemPage *pPage = pCur->pPage; lwr = 0; upr = pPage->nCell-1; while( lwr<=upr ){ int c; pCur->idx = (lwr+upr)/2; rc = compareKey(pCur, pKey, nKey, &c); if( rc ) return rc; if( c==0 ){ if( pRes ) *pRes = 0; return SQLITE_OK; } if( c<0 ){ lwr = pCur->idx+1; }else{ upr = pCur->idx-1; } } assert( lwr==upr+1 ); if( lwr>=pPage->nCell ){ chldPg = pPage->pStart->pgno; }else{ chldPg = pPage->aCell[lwr].pgno; } if( chldPg==0 ){ if( pRes ) *pRes = c; return SQLITE_OK; } rc = childPage(pCur, chldPg); if( rc ) return rc; } } /* ** Advance the cursor to the next entry in the database. If pRes!=NULL ** then set *pRes=0 on success and set *pRes=1 if the cursor was ** pointing to the last entry in the database. */ int sqliteBtreeNext(BtCursor *pCur, int *pRes){ MemPage *pPage; int rc; int moved = 0; if( pCur->skip_next ){ pCur->skip_next = 0; if( pRes ) *pRes = 0; return SQLITE_OK; } pPage = pCur->pPage; pCur->idx++; while( pCur->idx>=pPage->nCell ){ if( pCur->depth==0 ){ if( pRes ) *pRes = 1; return SQLITE_OK; } rc = parentPage(pCur); if( rc ) return rc; moved = 1; pPage = pCur->pPage; } if( moved ){ if( pRes ) *pRes = 0; return SQLITE_OK; } while( pCur->idx<pPage->nCell && pPage->aCell[pCur->idx].pgno>0 ){ rc = childPage(pCur, pPage->aCell[pCur->idx].pgno); if( rc ) return rc; pPage = pCur->pPage; } if( pRes ) *pRes = 0; return SQLITE_OK; } int sqliteBtreeInsert(BtCursor*, void *pKey, int nKey, void *pData, int nData); int sqliteBtreeDelete(BtCursor*); |
Changes to src/btree.h.
︙ | ︙ | |||
20 21 22 23 24 25 26 | ** drh@hwaci.com ** http://www.hwaci.com/drh/ ** ************************************************************************* ** This header file defines the interface that the sqlite B-Tree file ** subsystem. ** | | < < < < < < | | | | | 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | ** drh@hwaci.com ** http://www.hwaci.com/drh/ ** ************************************************************************* ** This header file defines the interface that the sqlite B-Tree file ** subsystem. ** ** @(#) $Id: btree.h,v 1.2 2001/05/24 21:06:36 drh Exp $ */ typedef struct Btree Btree; typedef struct BtCursor BtCursor; int sqliteBtreeOpen(const char *zFilename, int mode, Btree **ppBtree); int sqliteBtreeClose(Btree*); int sqliteBtreeBeginTrans(Btree*); int sqliteBtreeCommit(Btree*); int sqliteBtreeRollback(Btree*); int sqliteBtreeCursor(Btree*, BtCursor **ppCur); int sqliteBtreeMoveto(BtCursor*, void *pKey, int nKey, *pRes); int sqliteBtreeDelete(BtCursor*); int sqliteBtreeInsert(BtCursor*, void *pKey, int nKey, void *pData, int nData); int sqliteBtreeNext(BtCursor*, int *pRes); int sqliteBtreeKeySize(BtCursor*, int *pSize); int sqliteBtreeKey(BtCursor*, int offset, int amt, char *zBuf); int sqliteBtreeDataSize(BtCursor*, int *pSize); int sqliteBtreeData(BtCursor*, int offset, int amt, char *zBuf); int sqliteBtreeCloseCursor(BtCursor*); |
Changes to src/pager.c.
︙ | ︙ | |||
23 24 25 26 27 28 29 | ************************************************************************* ** This is the implementation of the page cache subsystem. ** ** The page cache is used to access a database file. The pager journals ** all writes in order to support rollback. Locking is used to limit ** access to one or more reader or one writer. ** | | | 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | ************************************************************************* ** This is the implementation of the page cache subsystem. ** ** The page cache is used to access a database file. The pager journals ** all writes in order to support rollback. Locking is used to limit ** access to one or more reader or one writer. ** ** @(#) $Id: pager.c,v 1.7 2001/05/24 21:06:36 drh Exp $ */ #include "sqliteInt.h" #include "pager.h" #include <fcntl.h> #include <sys/stat.h> #include <unistd.h> #include <assert.h> |
︙ | ︙ | |||
109 110 111 112 113 114 115 116 117 118 119 120 121 122 | struct Pager { char *zFilename; /* Name of the database file */ char *zJournal; /* Name of the journal file */ int fd, jfd; /* File descriptors for database and journal */ int dbSize; /* Number of pages in the file */ int origDbSize; /* dbSize before the current change */ int nExtra; /* Add this many bytes to each in-memory page */ int nPage; /* Total number of in-memory pages */ int nRef; /* Number of in-memory pages with PgHdr.nRef>0 */ int mxPage; /* Maximum number of pages to hold in cache */ int nHit, nMiss, nOvfl; /* Cache hits, missing, and LRU overflows */ unsigned char state; /* SQLITE_UNLOCK, _READLOCK or _WRITELOCK */ unsigned char errMask; /* One of several kinds of errors */ PgHdr *pFirst, *pLast; /* List of free pages */ | > | 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 | struct Pager { char *zFilename; /* Name of the database file */ char *zJournal; /* Name of the journal file */ int fd, jfd; /* File descriptors for database and journal */ int dbSize; /* Number of pages in the file */ int origDbSize; /* dbSize before the current change */ int nExtra; /* Add this many bytes to each in-memory page */ void (*xDestructor)(void*); /* Call this routine when freeing pages */ int nPage; /* Total number of in-memory pages */ int nRef; /* Number of in-memory pages with PgHdr.nRef>0 */ int mxPage; /* Maximum number of pages to hold in cache */ int nHit, nMiss, nOvfl; /* Cache hits, missing, and LRU overflows */ unsigned char state; /* SQLITE_UNLOCK, _READLOCK or _WRITELOCK */ unsigned char errMask; /* One of several kinds of errors */ PgHdr *pFirst, *pLast; /* List of free pages */ |
︙ | ︙ | |||
473 474 475 476 477 478 479 480 481 482 483 484 485 486 | pPager->errMask = 0; pPager->pFirst = 0; pPager->pLast = 0; memset(pPager->aHash, 0, sizeof(pPager->aHash)); *ppPager = pPager; return SQLITE_OK; } /* ** Return the total number of pages in the file opened by pPager. */ int sqlitepager_pagecount(Pager *pPager){ int n; struct stat statbuf; | > > > > > > > > > > > | 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 | pPager->errMask = 0; pPager->pFirst = 0; pPager->pLast = 0; memset(pPager->aHash, 0, sizeof(pPager->aHash)); *ppPager = pPager; return SQLITE_OK; } /* ** Set the destructor for this pager. If not NULL, the destructor is called ** when the reference count on the page reaches zero. ** ** The destructor is not called as a result sqlitepager_close(). ** Destructors are only called by sqlitepager_unref(). */ void sqlitepager_set_destructor(Pager *pPager, void (*xDesc)(void*)){ pPager->xDestructor = xDesc; } /* ** Return the total number of pages in the file opened by pPager. */ int sqlitepager_pagecount(Pager *pPager){ int n; struct stat statbuf; |
︙ | ︙ | |||
802 803 804 805 806 807 808 | /* Decrement the reference count for this page */ pPg = DATA_TO_PGHDR(pData); assert( pPg->nRef>0 ); pPager = pPg->pPager; pPg->nRef--; | | | > > > | 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 | /* Decrement the reference count for this page */ pPg = DATA_TO_PGHDR(pData); assert( pPg->nRef>0 ); pPager = pPg->pPager; pPg->nRef--; /* When the number of references to a page reach 0, call the ** destructor and add the page to the freelist. */ if( pPg->nRef==0 ){ pPg->pNextFree = 0; pPg->pPrevFree = pPager->pLast; pPager->pLast = pPg; if( pPg->pPrevFree ){ pPg->pPrevFree->pNextFree = pPg; }else{ pPager->pFirst = pPg; } if( pPager->xDestructor ){ pPager->xDestructor(pData); } /* When all pages reach the freelist, drop the read lock from ** the database file. */ pPager->nRef--; assert( pPager->nRef>=0 ); if( pPager->nRef==0 ){ |
︙ | ︙ |
Changes to src/pager.h.
︙ | ︙ | |||
21 22 23 24 25 26 27 | ** http://www.hwaci.com/drh/ ** ************************************************************************* ** This header file defines the interface that the sqlite page cache ** subsystem. The page cache subsystem reads and writes a file a page ** at a time and provides a journal for rollback. ** | | | > | 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | ** http://www.hwaci.com/drh/ ** ************************************************************************* ** This header file defines the interface that the sqlite page cache ** subsystem. The page cache subsystem reads and writes a file a page ** at a time and provides a journal for rollback. ** ** @(#) $Id: pager.h,v 1.4 2001/05/24 21:06:36 drh Exp $ */ /* ** The size of one page */ #define SQLITE_PAGE_SIZE 1024 /* ** The type used to represent a page number. The first page in a file ** is called page 1. 0 is used to represent "not a page". */ typedef unsigned int Pgno; /* ** Each open file is managed by a separate instance of the "Pager" structure. */ typedef struct Pager Pager; int sqlitepager_open(Pager **ppPager,const char *zFilename,int nPage,int nEx); void sqiltepager_set_destructor(Pager*, void(*)(void*)); int sqlitepager_close(Pager *pPager); int sqlitepager_get(Pager *pPager, Pgno pgno, void **ppPage); void *sqlitepager_lookup(Pager *pPager, Pgno pgno); int sqlitepager_unref(void*); Pgno sqlitepager_pagenumber(void*); int sqlitepager_write(void*); int sqlitepager_pagecount(Pager*); int sqlitepager_commit(Pager*); int sqlitepager_rollback(Pager*); int *sqlitepager_stats(Pager*); |
Changes to test/pager.test.
︙ | ︙ | |||
19 20 21 22 23 24 25 | # drh@hwaci.com # http://www.hwaci.com/drh/ # #*********************************************************************** # This file implements regression tests for SQLite library. The # focus of this script is page cache subsystem. # | | | 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | # drh@hwaci.com # http://www.hwaci.com/drh/ # #*********************************************************************** # This file implements regression tests for SQLite library. The # focus of this script is page cache subsystem. # # $Id: pager.test,v 1.5 2001/05/24 21:06:36 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl if {$dbprefix!="mem:" && [info commands pager_open]!=""} { |
︙ | ︙ | |||
62 63 64 65 66 67 68 | } {0} do_test pager-2.2 { set v [catch { set ::g1 [page_get $::p1 0] } msg] lappend v $msg } {1 SQLITE_ERROR} | | > > > > > > > > > > > > > > > > > > > > > > > | 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | } {0} do_test pager-2.2 { set v [catch { set ::g1 [page_get $::p1 0] } msg] lappend v $msg } {1 SQLITE_ERROR} do_test pager-2.3.1 { set ::gx [page_lookup $::p1 1] } {} do_test pager-2.3.2 { pager_stats $::p1 } {ref 0 page 0 max 10 size -1 state 0 err 0 hit 0 miss 0 ovfl 0} do_test pager-2.3.3 { set v [catch { set ::g1 [page_get $::p1 1] } msg] if {$v} {lappend v $msg} set v } {0} do_test pager-2.3.3 { pager_stats $::p1 } {ref 1 page 1 max 10 size 0 state 1 err 0 hit 0 miss 1 ovfl 0} do_test pager-2.3.4 { set ::gx [page_lookup $::p1 1] expr {$::gx!=""} } {1} do_test pager-2.3.5 { pager_stats $::p1 } {ref 1 page 1 max 10 size 0 state 1 err 0 hit 0 miss 1 ovfl 0} do_test pager-2.3.6 { expr $::g1==$::gx } {1} do_test pager-2.3.7 { page_unref $::gx pager_stats $::p1 } {ref 1 page 1 max 10 size 0 state 1 err 0 hit 0 miss 1 ovfl 0} do_test pager-2.4 { pager_stats $::p1 } {ref 1 page 1 max 10 size 0 state 1 err 0 hit 0 miss 1 ovfl 0} do_test pager-2.5 { pager_pagecount $::p1 } {0} do_test pager-2.6 { |
︙ | ︙ |