Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Enhance the performance of auto-vacuum databases by reducing the number of pointer-map entries written during tree balancing. Also fix bugs in balance_quick(). (CVS 2216) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
0ae29538ccccfc237904cbcfb4507074 |
User & Date: | danielk1977 2005-01-15 12:45:51.000 |
Context
2005-01-16
| ||
08:00 | Move duplicate code to update pointer-map wrt overflow pages into a function. (CVS 2217) (check-in: a5c2121410 user: danielk1977 tags: trunk) | |
2005-01-15
| ||
12:45 | Enhance the performance of auto-vacuum databases by reducing the number of pointer-map entries written during tree balancing. Also fix bugs in balance_quick(). (CVS 2216) (check-in: 0ae29538cc user: danielk1977 tags: trunk) | |
01:52 | Test coverage improvements. (CVS 2215) (check-in: 92f9d2b2f4 user: drh tags: trunk) | |
Changes
Changes to src/btree.c.
1 2 3 4 5 6 7 8 9 10 11 | /* ** 2004 April 6 ** ** The author disclaims copyright to this source code. In place of ** a legal notice, here is a blessing: ** ** May you do good and not evil. ** May you find forgiveness for yourself and forgive others. ** May you share freely, never taking more than you give. ** ************************************************************************* | | | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | /* ** 2004 April 6 ** ** The author disclaims copyright to this source code. In place of ** a legal notice, here is a blessing: ** ** May you do good and not evil. ** May you find forgiveness for yourself and forgive others. ** May you share freely, never taking more than you give. ** ************************************************************************* ** $Id: btree.c,v 1.234 2005/01/15 12:45:51 danielk1977 Exp $ ** ** This file implements a external (disk-based) database using BTrees. ** For a detailed discussion of BTrees, refer to ** ** Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3: ** "Sorting And Searching", pages 473-480. Addison-Wesley ** Publishing Company, Reading, Massachusetts. |
︙ | ︙ | |||
459 460 461 462 463 464 465 466 467 468 469 470 471 472 | */ static int ptrmapPut(Btree *pBt, Pgno key, u8 eType, Pgno pgno){ u8 *pPtrmap; /* The pointer map page */ Pgno iPtrmap; /* The pointer map page number */ int offset; /* Offset in pointer map page */ int rc; assert( key!=0 ); iPtrmap = PTRMAP_PAGENO(pBt->usableSize, key); rc = sqlite3pager_get(pBt->pPager, iPtrmap, (void **)&pPtrmap); if( rc!=SQLITE_OK ){ return rc; } offset = PTRMAP_PTROFFSET(pBt->usableSize, key); | > | 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 | */ static int ptrmapPut(Btree *pBt, Pgno key, u8 eType, Pgno pgno){ u8 *pPtrmap; /* The pointer map page */ Pgno iPtrmap; /* The pointer map page number */ int offset; /* Offset in pointer map page */ int rc; assert( pBt->autoVacuum ); assert( key!=0 ); iPtrmap = PTRMAP_PAGENO(pBt->usableSize, key); rc = sqlite3pager_get(pBt->pPager, iPtrmap, (void **)&pPtrmap); if( rc!=SQLITE_OK ){ return rc; } offset = PTRMAP_PTROFFSET(pBt->usableSize, key); |
︙ | ︙ | |||
637 638 639 640 641 642 643 644 645 646 647 648 649 650 | } #endif static int cellSizePtr(MemPage *pPage, u8 *pCell){ CellInfo info; parseCellPtr(pPage, pCell, &info); return info.nSize; } /* ** Do sanity checking on a page. Throw an exception if anything is ** not right. ** ** This routine is used for internal error checking only. It is omitted ** from most builds. | > > > > > > > > > > > > > | 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 | } #endif static int cellSizePtr(MemPage *pPage, u8 *pCell){ CellInfo info; parseCellPtr(pPage, pCell, &info); return info.nSize; } /* ** If pCell, part of pPage, contains a pointer to an overflow page, ** return the overflow page number. Otherwise return 0. */ static Pgno ovflPagePtr(MemPage *pPage, u8 *pCell){ CellInfo info; parseCellPtr(pPage, pCell, &info); if( (info.nData+(pPage->intKey?0:info.nKey))>info.nLocal ){ return get4byte(&pCell[info.iOverflow]); } return 0; } /* ** Do sanity checking on a page. Throw an exception if anything is ** not right. ** ** This routine is used for internal error checking only. It is omitted ** from most builds. |
︙ | ︙ | |||
1808 1809 1810 1811 1812 1813 1814 | */ do{ if( pFreeMemPage ){ releasePage(pFreeMemPage); pFreeMemPage = 0; } rc = allocatePage(pBt, &pFreeMemPage, &iFreePage, 0, 0); | | > > > | 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 | */ do{ if( pFreeMemPage ){ releasePage(pFreeMemPage); pFreeMemPage = 0; } rc = allocatePage(pBt, &pFreeMemPage, &iFreePage, 0, 0); if( rc!=SQLITE_OK ){ releasePage(pDbMemPage); goto autovacuum_out; } assert( iFreePage<=origSize ); }while( iFreePage>finSize ); releasePage(pFreeMemPage); pFreeMemPage = 0; rc = relocatePage(pBt, pDbMemPage, eType, iPtrPage, iFreePage); releasePage(pDbMemPage); |
︙ | ︙ | |||
3315 3316 3317 3318 3319 3320 3321 3322 3323 3324 3325 3326 3327 3328 3329 3330 3331 3332 3333 3334 3335 3336 3337 | #ifndef SQLITE_OMIT_AUTOVACUUM if( pBt->autoVacuum ){ return ptrmapPut(pBt, pgno, PTRMAP_BTREE, pNewParent->pgno); } #endif return SQLITE_OK; } /* ** Change the pParent pointer of all children of pPage to point back ** to pPage. ** ** In other words, for every child of pPage, invoke reparentPage() ** to make sure that each child knows that pPage is its parent. ** ** This routine gets called after you memcpy() one page into ** another. */ static int reparentChildPages(MemPage *pPage){ int i; Btree *pBt = pPage->pBt; int rc = SQLITE_OK; | > > < < < < < < < < < < < < < < < < < < < < < | 3332 3333 3334 3335 3336 3337 3338 3339 3340 3341 3342 3343 3344 3345 3346 3347 3348 3349 3350 3351 3352 3353 3354 3355 3356 3357 3358 3359 3360 3361 3362 3363 3364 3365 3366 3367 3368 3369 3370 3371 | #ifndef SQLITE_OMIT_AUTOVACUUM if( pBt->autoVacuum ){ return ptrmapPut(pBt, pgno, PTRMAP_BTREE, pNewParent->pgno); } #endif return SQLITE_OK; } /* ** Change the pParent pointer of all children of pPage to point back ** to pPage. ** ** In other words, for every child of pPage, invoke reparentPage() ** to make sure that each child knows that pPage is its parent. ** ** This routine gets called after you memcpy() one page into ** another. */ static int reparentChildPages(MemPage *pPage){ int i; Btree *pBt = pPage->pBt; int rc = SQLITE_OK; if( pPage->leaf ) return SQLITE_OK; for(i=0; i<pPage->nCell; i++){ u8 *pCell = findCell(pPage, i); if( !pPage->leaf ){ rc = reparentPage(pBt, get4byte(pCell), pPage, i); if( rc!=SQLITE_OK ) return rc; } } if( !pPage->leaf ){ rc = reparentPage(pBt, get4byte(&pPage->aData[pPage->hdrOffset+8]), pPage, i); pPage->idxShift = 0; } return rc; |
︙ | ︙ | |||
3578 3579 3580 3581 3582 3583 3584 3585 3586 3587 3588 3589 3590 3591 3592 | static int balance_quick(MemPage *pPage, MemPage *pParent){ int rc; MemPage *pNew; Pgno pgnoNew; u8 *pCell; int szCell; CellInfo info; u8 parentCell[64]; /* How big should this be? */ int parentIdx = pParent->nCell; int parentSize; /* Allocate a new page. Insert the overflow cell from pPage ** into it. Then remove the overflow cell from pPage. */ | > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 3576 3577 3578 3579 3580 3581 3582 3583 3584 3585 3586 3587 3588 3589 3590 3591 3592 3593 3594 3595 3596 3597 3598 3599 3600 3601 3602 3603 3604 3605 3606 3607 3608 3609 3610 3611 3612 3613 3614 3615 3616 3617 3618 3619 3620 3621 3622 3623 3624 3625 3626 3627 3628 3629 3630 3631 3632 3633 3634 3635 3636 3637 3638 3639 3640 3641 3642 3643 3644 3645 3646 3647 3648 3649 3650 3651 3652 3653 3654 3655 3656 3657 3658 3659 3660 3661 3662 3663 | static int balance_quick(MemPage *pPage, MemPage *pParent){ int rc; MemPage *pNew; Pgno pgnoNew; u8 *pCell; int szCell; CellInfo info; Btree *pBt = pPage->pBt; u8 parentCell[64]; /* How big should this be? */ int parentIdx = pParent->nCell; int parentSize; /* Allocate a new page. Insert the overflow cell from pPage ** into it. Then remove the overflow cell from pPage. */ rc = allocatePage(pBt, &pNew, &pgnoNew, 0, 0); if( rc!=SQLITE_OK ){ return rc; } pCell = pPage->aOvfl[0].pCell; szCell = cellSizePtr(pPage, pCell); zeroPage(pNew, pPage->aData[0]); assemblePage(pNew, 1, &pCell, &szCell); pPage->nOverflow = 0; /* pPage is currently the right-child of pParent. Change this ** so that the right-child is the new page allocated above and ** pPage is the next-to-right child. Then balance() the parent ** page, in case it is now overfull. */ assert( pPage->nCell>0 ); parseCellPtr(pPage, findCell(pPage, pPage->nCell-1), &info); rc = fillInCell(pParent, parentCell, 0, info.nKey, 0, 0, &parentSize); if( rc!=SQLITE_OK ){ return SQLITE_OK; } assert( parentSize<64 ); rc = insertCell(pParent, parentIdx, parentCell, parentSize, 0, 4); if( rc!=SQLITE_OK ){ return SQLITE_OK; } put4byte(findOverflowCell(pParent,parentIdx), pPage->pgno); put4byte(&pParent->aData[pParent->hdrOffset+8], pgnoNew); pNew->pParent = pParent; sqlite3pager_ref(pParent->aData); if( pBt->autoVacuum ){ rc = ptrmapPut(pBt, pgnoNew, PTRMAP_BTREE, pParent->pgno); if( rc!=SQLITE_OK ){ return rc; } pCell = findCell(pNew, 0); parseCellPtr(pNew, pCell, &info); if( info.nData>info.nLocal ){ Pgno pgnoOvfl = get4byte(&pCell[info.iOverflow]); rc = ptrmapPut(pBt, pgnoOvfl, PTRMAP_OVERFLOW1, pgnoNew); if( rc!=SQLITE_OK ){ return rc; } } } releasePage(pNew); return balance(pParent, 0); } /* ** The ISAUTOVACUUM macro is used within balance_nonroot() to determine ** if the database supports auto-vacuum or not. Because it is used ** within an expression that is an argument to another macro ** (sqliteMallocRaw), it is not possible to use conditional compilation. ** So, this macro is defined instead. */ #ifndef SQLITE_OMIT_AUTOVACUUM #define ISAUTOVACUUM (pBt->autoVacuum) #else #define ISAUTOVACUUM 0 #endif /* ** This routine redistributes Cells on pPage and up to NN*2 siblings ** of pPage so that all pages have about the same amount of free space. ** Usually NN siblings on either side of pPage is used in the balancing, ** though more siblings might come from one side if pPage is the first ** or last child of its parent. If pPage has fewer than 2*NN siblings ** (something which can only happen if pPage is the root page or a |
︙ | ︙ | |||
3681 3682 3683 3684 3685 3686 3687 3688 3689 3690 3691 3692 3693 3694 | u8 *apDiv[NB]; /* Divider cells in pParent */ int cntNew[NB+2]; /* Index in aCell[] of cell after i-th page */ int szNew[NB+2]; /* Combined size of cells place on i-th page */ u8 **apCell; /* All cells begin balanced */ int *szCell; /* Local size of all cells in apCell[] */ u8 *aCopy[NB]; /* Space for holding data of apCopy[] */ u8 *aSpace; /* Space to hold copies of dividers cells */ /* ** Find the parent page. */ assert( pPage->isInit ); assert( sqlite3pager_iswriteable(pPage->aData) ); pBt = pPage->pBt; | > > > | 3710 3711 3712 3713 3714 3715 3716 3717 3718 3719 3720 3721 3722 3723 3724 3725 3726 | u8 *apDiv[NB]; /* Divider cells in pParent */ int cntNew[NB+2]; /* Index in aCell[] of cell after i-th page */ int szNew[NB+2]; /* Combined size of cells place on i-th page */ u8 **apCell; /* All cells begin balanced */ int *szCell; /* Local size of all cells in apCell[] */ u8 *aCopy[NB]; /* Space for holding data of apCopy[] */ u8 *aSpace; /* Space to hold copies of dividers cells */ #ifndef SQLITE_OMIT_VACUUM u8 *aFrom = 0; #endif /* ** Find the parent page. */ assert( pPage->isInit ); assert( sqlite3pager_iswriteable(pPage->aData) ); pBt = pPage->pBt; |
︙ | ︙ | |||
3707 3708 3709 3710 3711 3712 3713 3714 3715 3716 3717 3718 3719 3720 3721 3722 3723 3724 3725 3726 3727 3728 3729 3730 3731 3732 3733 3734 3735 3736 3737 3738 3739 3740 3741 3742 3743 3744 | ** packing of data in the common case. */ if( pPage->leaf && pPage->intKey && pPage->leafData && pPage->nOverflow==1 && pPage->aOvfl[0].idx==pPage->nCell && get4byte(&pParent->aData[pParent->hdrOffset+8])==pPage->pgno ){ return balance_quick(pPage, pParent); } #endif /* ** Allocate space for memory structures */ mxCellPerPage = MX_CELL(pBt); apCell = sqliteMallocRaw( (mxCellPerPage+2)*NB*(sizeof(u8*)+sizeof(int)) + sizeof(MemPage)*NB + pBt->psAligned*(5+NB) ); if( apCell==0 ){ return SQLITE_NOMEM; } szCell = (int*)&apCell[(mxCellPerPage+2)*NB]; aCopy[0] = (u8*)&szCell[(mxCellPerPage+2)*NB]; for(i=1; i<NB; i++){ aCopy[i] = &aCopy[i-1][pBt->psAligned+sizeof(MemPage)]; } aSpace = &aCopy[NB-1][pBt->psAligned+sizeof(MemPage)]; /* ** Find the cell in the parent page whose left child points back ** to pPage. The "idx" variable is the index of that cell. If pPage ** is the rightmost child of pParent then set idx to pParent->nCell */ if( pParent->idxShift ){ | > > > > > > > > > > > | 3739 3740 3741 3742 3743 3744 3745 3746 3747 3748 3749 3750 3751 3752 3753 3754 3755 3756 3757 3758 3759 3760 3761 3762 3763 3764 3765 3766 3767 3768 3769 3770 3771 3772 3773 3774 3775 3776 3777 3778 3779 3780 3781 3782 3783 3784 3785 3786 3787 | ** packing of data in the common case. */ if( pPage->leaf && pPage->intKey && pPage->leafData && pPage->nOverflow==1 && pPage->aOvfl[0].idx==pPage->nCell && pPage->pParent->pgno!=1 && get4byte(&pParent->aData[pParent->hdrOffset+8])==pPage->pgno ){ /* ** TODO: Check the siblings to the left of pPage. It may be that ** they are not full and no new page is required. */ return balance_quick(pPage, pParent); } #endif /* ** Allocate space for memory structures */ mxCellPerPage = MX_CELL(pBt); apCell = sqliteMallocRaw( (mxCellPerPage+2)*NB*(sizeof(u8*)+sizeof(int)) + sizeof(MemPage)*NB + pBt->psAligned*(5+NB) + (ISAUTOVACUUM ? (mxCellPerPage+2)*NN*2 : 0) ); if( apCell==0 ){ return SQLITE_NOMEM; } szCell = (int*)&apCell[(mxCellPerPage+2)*NB]; aCopy[0] = (u8*)&szCell[(mxCellPerPage+2)*NB]; for(i=1; i<NB; i++){ aCopy[i] = &aCopy[i-1][pBt->psAligned+sizeof(MemPage)]; } aSpace = &aCopy[NB-1][pBt->psAligned+sizeof(MemPage)]; #ifndef SQLITE_OMIT_AUTOVACUUM if( pBt->autoVacuum ){ aFrom = &aSpace[5*pBt->psAligned]; } #endif /* ** Find the cell in the parent page whose left child points back ** to pPage. The "idx" variable is the index of that cell. If pPage ** is the rightmost child of pParent then set idx to pParent->nCell */ if( pParent->idxShift ){ |
︙ | ︙ | |||
3832 3833 3834 3835 3836 3837 3838 3839 3840 3841 3842 3843 3844 3845 3846 3847 3848 3849 3850 3851 3852 3853 3854 3855 3856 3857 3858 3859 3860 3861 3862 3863 3864 | leafData = pPage->leafData && pPage->leaf; for(i=0; i<nOld; i++){ MemPage *pOld = apCopy[i]; int limit = pOld->nCell+pOld->nOverflow; for(j=0; j<limit; j++){ apCell[nCell] = findOverflowCell(pOld, j); szCell[nCell] = cellSizePtr(pOld, apCell[nCell]); nCell++; } if( i<nOld-1 ){ int sz = cellSizePtr(pParent, apDiv[i]); if( leafData ){ /* With the LEAFDATA flag, pParent cells hold only INTKEYs that ** are duplicates of keys on the child pages. We need to remove ** the divider cells from pParent, but the dividers cells are not ** added to apCell[] because they are duplicates of child cells. */ dropCell(pParent, nxDiv, sz); }else{ u8 *pTemp; szCell[nCell] = sz; pTemp = &aSpace[iSpace]; iSpace += sz; assert( iSpace<=pBt->psAligned*5 ); memcpy(pTemp, apDiv[i], sz); apCell[nCell] = pTemp+leafCorrection; dropCell(pParent, nxDiv, sz); szCell[nCell] -= leafCorrection; assert( get4byte(pTemp)==pgnoOld[i] ); if( !pOld->leaf ){ assert( leafCorrection==0 ); /* The right pointer of the child page pOld becomes the left ** pointer of the divider cell */ | > > > > > > > > > > > > > > > > > | 3875 3876 3877 3878 3879 3880 3881 3882 3883 3884 3885 3886 3887 3888 3889 3890 3891 3892 3893 3894 3895 3896 3897 3898 3899 3900 3901 3902 3903 3904 3905 3906 3907 3908 3909 3910 3911 3912 3913 3914 3915 3916 3917 3918 3919 3920 3921 3922 3923 3924 | leafData = pPage->leafData && pPage->leaf; for(i=0; i<nOld; i++){ MemPage *pOld = apCopy[i]; int limit = pOld->nCell+pOld->nOverflow; for(j=0; j<limit; j++){ apCell[nCell] = findOverflowCell(pOld, j); szCell[nCell] = cellSizePtr(pOld, apCell[nCell]); #ifndef SQLITE_OMIT_AUTOVACUUM if( pBt->autoVacuum ){ int a; aFrom[nCell] = i; for(a=0; a<pOld->nOverflow; a++){ if( pOld->aOvfl[a].pCell==apCell[nCell] ){ aFrom[nCell] = 0xFF; break; } } } #endif nCell++; } if( i<nOld-1 ){ int sz = cellSizePtr(pParent, apDiv[i]); if( leafData ){ /* With the LEAFDATA flag, pParent cells hold only INTKEYs that ** are duplicates of keys on the child pages. We need to remove ** the divider cells from pParent, but the dividers cells are not ** added to apCell[] because they are duplicates of child cells. */ dropCell(pParent, nxDiv, sz); }else{ u8 *pTemp; szCell[nCell] = sz; pTemp = &aSpace[iSpace]; iSpace += sz; assert( iSpace<=pBt->psAligned*5 ); memcpy(pTemp, apDiv[i], sz); apCell[nCell] = pTemp+leafCorrection; #ifndef SQLITE_OMIT_AUTOVACUUM if( pBt->autoVacuum ){ aFrom[nCell] = 0xFF; } #endif dropCell(pParent, nxDiv, sz); szCell[nCell] -= leafCorrection; assert( get4byte(pTemp)==pgnoOld[i] ); if( !pOld->leaf ){ assert( leafCorrection==0 ); /* The right pointer of the child page pOld becomes the left ** pointer of the divider cell */ |
︙ | ︙ | |||
4010 4011 4012 4013 4014 4015 4016 4017 4018 4019 | /* ** Evenly distribute the data in apCell[] across the new pages. ** Insert divider cells into pParent as necessary. */ j = 0; for(i=0; i<nNew; i++){ MemPage *pNew = apNew[i]; assert( pNew->pgno==pgnoNew[i] ); assemblePage(pNew, cntNew[i]-j, &apCell[j], &szCell[j]); | > < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 4070 4071 4072 4073 4074 4075 4076 4077 4078 4079 4080 4081 4082 4083 4084 4085 4086 4087 4088 4089 4090 4091 4092 4093 4094 4095 4096 4097 4098 4099 4100 4101 4102 4103 4104 4105 4106 4107 4108 4109 4110 4111 4112 4113 4114 4115 4116 4117 4118 4119 4120 4121 4122 4123 4124 4125 4126 4127 4128 4129 4130 4131 4132 4133 4134 4135 4136 4137 4138 4139 4140 4141 4142 4143 4144 4145 4146 4147 4148 4149 4150 4151 4152 4153 4154 4155 4156 4157 4158 4159 4160 4161 4162 4163 | /* ** Evenly distribute the data in apCell[] across the new pages. ** Insert divider cells into pParent as necessary. */ j = 0; for(i=0; i<nNew; i++){ /* Assemble the new sibling page. */ MemPage *pNew = apNew[i]; assert( pNew->pgno==pgnoNew[i] ); assemblePage(pNew, cntNew[i]-j, &apCell[j], &szCell[j]); assert( pNew->nCell>0 ); assert( pNew->nOverflow==0 ); #ifndef SQLITE_OMIT_AUTOVACUUM /* If this is an auto-vacuum database, update the pointer map entries ** that point to the siblings that were rearranged. These can be: left ** children of cells, the right-child of the page, or overflow pages ** pointed to by cells. */ if( pBt->autoVacuum ){ for(k=j; k<cntNew[i]; k++){ if( aFrom[k]==0xFF || apCopy[aFrom[k]]->pgno!=pNew->pgno ){ Pgno ovfl = ovflPagePtr(pNew, findCell(pNew, k-j)); if( ovfl ){ rc = ptrmapPut(pBt, ovfl, PTRMAP_OVERFLOW1, pNew->pgno); if( rc!=SQLITE_OK ){ goto balance_cleanup; } } } } } #endif j = cntNew[i]; /* If the sibling page assembled above was not the right-most sibling, ** insert a divider cell into the parent page. */ if( i<nNew-1 && j<nCell ){ u8 *pCell; u8 *pTemp; int sz; pCell = apCell[j]; sz = szCell[j] + leafCorrection; if( !pNew->leaf ){ memcpy(&pNew->aData[8], pCell, 4); pTemp = 0; }else if( leafData ){ /* If the tree is a leaf-data tree, and the siblings are leaves, ** then there is no divider cell in apCell[]. Instead, the divider ** cell consists of the integer key for the right-most cell of ** the sibling-page assembled above only. */ CellInfo info; j--; parseCellPtr(pNew, apCell[j], &info); pCell = &aSpace[iSpace]; fillInCell(pParent, pCell, 0, info.nKey, 0, 0, &sz); iSpace += sz; assert( iSpace<=pBt->psAligned*5 ); pTemp = 0; }else{ pCell -= 4; pTemp = &aSpace[iSpace]; iSpace += sz; assert( iSpace<=pBt->psAligned*5 ); } rc = insertCell(pParent, nxDiv, pCell, sz, pTemp, 4); if( rc!=SQLITE_OK ) goto balance_cleanup; put4byte(findOverflowCell(pParent,nxDiv), pNew->pgno); #ifndef SQLITE_OMIT_AUTOVACUUM /* If this is an auto-vacuum database, and not a leaf-data tree, ** then update the pointer map with an entry for the overflow page ** that the cell just inserted points to (if any). */ if( pBt->autoVacuum && !leafData ){ Pgno ovfl = ovflPagePtr(pParent, findOverflowCell(pParent, nxDiv)); if( ovfl ){ rc = ptrmapPut(pBt, ovfl, PTRMAP_OVERFLOW1, pParent->pgno); if( rc!=SQLITE_OK ){ goto balance_cleanup; } } } #endif j++; nxDiv++; } } assert( j==nCell ); if( (pageFlags & PTF_LEAF)==0 ){ memcpy(&apNew[nNew-1]->aData[8], &apCopy[nOld-1]->aData[8], 4); |
︙ | ︙ | |||
4072 4073 4074 4075 4076 4077 4078 | if( rc!=SQLITE_OK ) goto balance_cleanup; } rc = reparentChildPages(pParent); if( rc!=SQLITE_OK ) goto balance_cleanup; /* ** Balance the parent page. Note that the current page (pPage) might | | | 4179 4180 4181 4182 4183 4184 4185 4186 4187 4188 4189 4190 4191 4192 4193 | if( rc!=SQLITE_OK ) goto balance_cleanup; } rc = reparentChildPages(pParent); if( rc!=SQLITE_OK ) goto balance_cleanup; /* ** Balance the parent page. Note that the current page (pPage) might ** have been added to the freelist so it might no longer be initialized. ** But the parent page will always be initialized. */ assert( pParent->isInit ); /* assert( pPage->isInit ); // No! pPage might have been added to freelist */ /* pageIntegrity(pPage); // No! pPage might have been added to freelist */ rc = balance(pParent, 0); |
︙ | ︙ | |||
4110 4111 4112 4113 4114 4115 4116 4117 4118 4119 4120 4121 4122 4123 | MemPage *pChild; /* The only child page of pPage */ Pgno pgnoChild; /* Page number for pChild */ int rc = SQLITE_OK; /* Return code from subprocedures */ Btree *pBt; /* The main BTree structure */ int mxCellPerPage; /* Maximum number of cells per page */ u8 **apCell; /* All cells from pages being balanced */ int *szCell; /* Local size of all cells */ assert( pPage->pParent==0 ); assert( pPage->nCell==0 ); pBt = pPage->pBt; mxCellPerPage = MX_CELL(pBt); apCell = sqliteMallocRaw( mxCellPerPage*(sizeof(u8*)+sizeof(int)) ); if( apCell==0 ) return SQLITE_NOMEM; | > | 4217 4218 4219 4220 4221 4222 4223 4224 4225 4226 4227 4228 4229 4230 4231 | MemPage *pChild; /* The only child page of pPage */ Pgno pgnoChild; /* Page number for pChild */ int rc = SQLITE_OK; /* Return code from subprocedures */ Btree *pBt; /* The main BTree structure */ int mxCellPerPage; /* Maximum number of cells per page */ u8 **apCell; /* All cells from pages being balanced */ int *szCell; /* Local size of all cells */ int i; assert( pPage->pParent==0 ); assert( pPage->nCell==0 ); pBt = pPage->pBt; mxCellPerPage = MX_CELL(pBt); apCell = sqliteMallocRaw( mxCellPerPage*(sizeof(u8*)+sizeof(int)) ); if( apCell==0 ) return SQLITE_NOMEM; |
︙ | ︙ | |||
4174 4175 4176 4177 4178 4179 4180 4181 4182 4183 4184 4185 4186 4187 | rc = initPage(pPage, 0); assert( rc==SQLITE_OK ); freePage(pChild); TRACE(("BALANCE: transfer child %d into root %d\n", pChild->pgno, pPage->pgno)); } rc = reparentChildPages(pPage); if( rc!=SQLITE_OK ) goto end_shallow_balance; releasePage(pChild); } end_shallow_balance: sqliteFree(apCell); return rc; } | > > > > > > > > > > > > > > | 4282 4283 4284 4285 4286 4287 4288 4289 4290 4291 4292 4293 4294 4295 4296 4297 4298 4299 4300 4301 4302 4303 4304 4305 4306 4307 4308 4309 | rc = initPage(pPage, 0); assert( rc==SQLITE_OK ); freePage(pChild); TRACE(("BALANCE: transfer child %d into root %d\n", pChild->pgno, pPage->pgno)); } rc = reparentChildPages(pPage); assert( pPage->nOverflow==0 ); #ifndef SQLITE_OMIT_AUTOVACUUM if( pBt->autoVacuum ){ for(i=0; i<pPage->nCell; i++){ Pgno ovfl = ovflPagePtr(pPage, findCell(pPage, i)); if( ovfl ){ rc = ptrmapPut(pBt, ovfl, PTRMAP_OVERFLOW1, pPage->pgno); if( rc!=SQLITE_OK ){ goto end_shallow_balance; } } } } #endif if( rc!=SQLITE_OK ) goto end_shallow_balance; releasePage(pChild); } end_shallow_balance: sqliteFree(apCell); return rc; } |
︙ | ︙ | |||
4228 4229 4230 4231 4232 4233 4234 4235 4236 4237 4238 4239 4240 4241 | if( pChild->nOverflow ){ pChild->nFree = 0; } assert( pChild->nCell==pPage->nCell ); zeroPage(pPage, pChild->aData[0] & ~PTF_LEAF); put4byte(&pPage->aData[pPage->hdrOffset+8], pgnoChild); TRACE(("BALANCE: copy root %d into %d\n", pPage->pgno, pChild->pgno)); rc = balance_nonroot(pChild); releasePage(pChild); return rc; } /* ** Decide if the page pPage needs to be balanced. If balancing is | > > > > > > > > > > > > | 4350 4351 4352 4353 4354 4355 4356 4357 4358 4359 4360 4361 4362 4363 4364 4365 4366 4367 4368 4369 4370 4371 4372 4373 4374 4375 | if( pChild->nOverflow ){ pChild->nFree = 0; } assert( pChild->nCell==pPage->nCell ); zeroPage(pPage, pChild->aData[0] & ~PTF_LEAF); put4byte(&pPage->aData[pPage->hdrOffset+8], pgnoChild); TRACE(("BALANCE: copy root %d into %d\n", pPage->pgno, pChild->pgno)); if( pBt->autoVacuum ){ int i; rc = ptrmapPut(pBt, pChild->pgno, PTRMAP_BTREE, pPage->pgno); if( rc ) return rc; for(i=0; i<pChild->nCell; i++){ Pgno pgno = ovflPagePtr(pChild, findOverflowCell(pChild, i)); if( pgno ){ rc = ptrmapPut(pBt, pgno, PTRMAP_OVERFLOW1, pChild->pgno); if( rc ) return rc; } } } rc = balance_nonroot(pChild); releasePage(pChild); return rc; } /* ** Decide if the page pPage needs to be balanced. If balancing is |
︙ | ︙ |
Changes to test/autovacuum.test.
1 2 3 4 5 6 7 8 9 10 11 12 13 | # 2001 September 15 # # The author disclaims copyright to this source code. In place of # a legal notice, here is a blessing: # # May you do good and not evil. # May you find forgiveness for yourself and forgive others. # May you share freely, never taking more than you give. # #*********************************************************************** # This file implements regression tests for SQLite library. The # focus of this file is testing the SELECT statement. # | | | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | # 2001 September 15 # # The author disclaims copyright to this source code. In place of # a legal notice, here is a blessing: # # May you do good and not evil. # May you find forgiveness for yourself and forgive others. # May you share freely, never taking more than you give. # #*********************************************************************** # This file implements regression tests for SQLite library. The # focus of this file is testing the SELECT statement. # # $Id: autovacuum.test,v 1.14 2005/01/15 12:45:51 danielk1977 Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl # If this build of the library does not support auto-vacuum, omit this # whole file. ifcapable {!autovacuum} { |
︙ | ︙ | |||
56 57 58 59 60 61 62 63 64 65 66 67 68 69 | lappend delete_orders {20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1} lappend delete_orders {8 18 2 4 14 11 13 3 10 7 9 5 12 17 19 15 20 6 16 1} lappend delete_orders {10 3 11 17 19 20 7 4 13 6 1 14 16 12 9 18 8 15 5 2} lappend delete_orders {{1 2 3 4 5 6 7 8 9 10} {11 12 13 14 15 16 17 18 19 20}} lappend delete_orders {{19 8 17 15} {16 11 9 14} {18 5 3 1} {13 20 7 2} {6 12}} # The length of each table entry. set ENTRY_LEN 3500 do_test autovacuum-1.1 { execsql { PRAGMA auto_vacuum = 1; CREATE TABLE av1(a); CREATE INDEX av1_idx ON av1(a); | > | 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | lappend delete_orders {20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1} lappend delete_orders {8 18 2 4 14 11 13 3 10 7 9 5 12 17 19 15 20 6 16 1} lappend delete_orders {10 3 11 17 19 20 7 4 13 6 1 14 16 12 9 18 8 15 5 2} lappend delete_orders {{1 2 3 4 5 6 7 8 9 10} {11 12 13 14 15 16 17 18 19 20}} lappend delete_orders {{19 8 17 15} {16 11 9 14} {18 5 3 1} {13 20 7 2} {6 12}} # The length of each table entry. # set ENTRY_LEN 3500 set ENTRY_LEN 3500 do_test autovacuum-1.1 { execsql { PRAGMA auto_vacuum = 1; CREATE TABLE av1(a); CREATE INDEX av1_idx ON av1(a); |
︙ | ︙ |
Changes to test/autovacuum_ioerr2.test.
︙ | ︙ | |||
11 12 13 14 15 16 17 | # This file implements regression tests for SQLite library. The # focus of this file is testing for correct handling of I/O errors # such as writes failing because the disk is full. # # The tests in this file use special facilities that are only # available in the SQLite test fixture. # | | | 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | # This file implements regression tests for SQLite library. The # focus of this file is testing for correct handling of I/O errors # such as writes failing because the disk is full. # # The tests in this file use special facilities that are only # available in the SQLite test fixture. # # $Id: autovacuum_ioerr2.test,v 1.2 2005/01/15 12:45:51 danielk1977 Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl proc opendb {} { catch {file delete -force test.db} catch {file delete -force test.db-journal} |
︙ | ︙ | |||
73 74 75 76 77 78 79 | } for {set i 0} {$i<150} {incr i} { execsql { INSERT INTO abc VALUES(randstr(100,100)); } } execsql COMMIT | < | | 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 | } for {set i 0} {$i<150} {incr i} { execsql { INSERT INTO abc VALUES(randstr(100,100)); } } execsql COMMIT } {} do_test autovacuum-ioerr2-2.$n.2 [subst { set ::sqlite_io_error_pending $n }] $n do_test autovacuum-ioerr2-2.$n.3 { set r [catch {db eval { BEGIN; DELETE FROM abc WHERE length(a)>100; |
︙ | ︙ |
Changes to test/crash.test.
︙ | ︙ | |||
16 17 18 19 20 21 22 | # module "crashtest" compiled with the special "os_test.c" backend is used. # The os_test.c simulates the kind of file corruption that can occur # when writes are happening at the moment of power loss. # # The special crash-test module with its os_test.c backend only works # on Unix. # | | | 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | # module "crashtest" compiled with the special "os_test.c" backend is used. # The os_test.c simulates the kind of file corruption that can occur # when writes are happening at the moment of power loss. # # The special crash-test module with its os_test.c backend only works # on Unix. # # $Id: crash.test,v 1.15 2005/01/15 12:45:51 danielk1977 Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl # set repeats 100 set repeats 10 |
︙ | ︙ | |||
170 171 172 173 174 175 176 | execsql "INSERT INTO abc VALUES($n, [expr 2*$n], [expr 3*$n])" } execsql { COMMIT } set ::sig [signature] execsql { SELECT sum(a), sum(b), sum(c) from abc } } {499500.0 999000.0 1498500.0} do_test crash-2.2 { | | | | 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 | execsql "INSERT INTO abc VALUES($n, [expr 2*$n], [expr 3*$n])" } execsql { COMMIT } set ::sig [signature] execsql { SELECT sum(a), sum(b), sum(c) from abc } } {499500.0 999000.0 1498500.0} do_test crash-2.2 { expr ([file size test.db] / 1024)>16 } {1} do_test crash-2.3 { crashsql 2 test.db-journal { DELETE FROM abc WHERE a < 800; } } {1 {child process exited abnormally}} do_test crash-2.4 { signature |
︙ | ︙ | |||
210 211 212 213 214 215 216 | execsql { INSERT INTO abc SELECT * FROM abc; INSERT INTO abc SELECT * FROM abc; INSERT INTO abc SELECT * FROM abc; INSERT INTO abc SELECT * FROM abc; INSERT INTO abc SELECT * FROM abc; } | | | | 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 | execsql { INSERT INTO abc SELECT * FROM abc; INSERT INTO abc SELECT * FROM abc; INSERT INTO abc SELECT * FROM abc; INSERT INTO abc SELECT * FROM abc; INSERT INTO abc SELECT * FROM abc; } expr ([file size test.db] / 1024) > 450 } {1} for {set i 1} {$i < $repeats} {incr i} { set sig [signature] do_test crash-3.$i.1 { crashsql [expr $i%5 + 1] test.db-journal " BEGIN; SELECT random() FROM abc LIMIT $i; INSERT INTO abc VALUES(randstr(10,10), 0, 0); |
︙ | ︙ | |||
239 240 241 242 243 244 245 | # crash-4.1.*: Test recovery when crash occurs during sync() of the # main database journal file. # crash-4.2.*: Test recovery when crash occurs during sync() of an # attached database journal file. # crash-4.3.*: Test recovery when crash occurs during sync() of the master # journal file. # | < < < < | | | 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 | # crash-4.1.*: Test recovery when crash occurs during sync() of the # main database journal file. # crash-4.2.*: Test recovery when crash occurs during sync() of an # attached database journal file. # crash-4.3.*: Test recovery when crash occurs during sync() of the master # journal file. # do_test crash-4.0 { file delete -force test2.db file delete -force test2.db-journal execsql { ATTACH 'test2.db' AS aux; PRAGMA aux.default_cache_size = 10; CREATE TABLE aux.abc2 AS SELECT 2*a as a, 2*b as b, 2*c as c FROM abc; } expr ([file size test2.db] / 1024) > 450 } {1} for {set i 1} {$i<$repeats} {incr i} { set sig [signature] set sig2 [signature2] do_test crash-4.1.$i.1 { set c [crashsql $i test.db-journal " ATTACH 'test2.db' AS aux; |
︙ | ︙ |