Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Remove the MemPage.idxShift variable. It is no longer required. (CVS 5750) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
7354abd03be756b1d7d0a3d5b8958f5c |
User & Date: | danielk1977 2008-09-29 15:53:26.000 |
Context
2008-09-29
| ||
16:41 | Remove the reparentPage() and reparentChildPages() functions from btree.c. All calls to these functions can now be replaced by a call to setChildPtrmaps(). (CVS 5751) (check-in: 35e8e4dcd2 user: danielk1977 tags: trunk) | |
15:53 | Remove the MemPage.idxShift variable. It is no longer required. (CVS 5750) (check-in: 7354abd03b user: danielk1977 tags: trunk) | |
14:27 | Do not run vacuum.test as part of the "exclusive" permutation test. (CVS 5749) (check-in: 2fb15ae9e9 user: danielk1977 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.519 2008/09/29 15:53:26 danielk1977 Exp $ ** ** This file implements a external (disk-based) database using BTrees. ** See the header comment on "btreeInt.h" for additional information. ** Including a description of file format and an overview of operation. */ #include "btreeInt.h" |
︙ | ︙ | |||
940 941 942 943 944 945 946 | hdr = pPage->hdrOffset; data = pPage->aData; if( decodeFlags(pPage, data[hdr]) ) return SQLITE_CORRUPT_BKPT; assert( pBt->pageSize>=512 && pBt->pageSize<=32768 ); pPage->maskPage = pBt->pageSize - 1; pPage->nOverflow = 0; | < | 940 941 942 943 944 945 946 947 948 949 950 951 952 953 | hdr = pPage->hdrOffset; data = pPage->aData; if( decodeFlags(pPage, data[hdr]) ) return SQLITE_CORRUPT_BKPT; assert( pBt->pageSize>=512 && pBt->pageSize<=32768 ); pPage->maskPage = pBt->pageSize - 1; pPage->nOverflow = 0; usableSize = pBt->usableSize; pPage->cellOffset = cellOffset = hdr + 12 - 4*pPage->leaf; top = get2byte(&data[hdr+5]); pPage->nCell = get2byte(&data[hdr+3]); if( pPage->nCell>MX_CELL(pBt) ){ /* To many cells for a single page. The page must be corrupt */ return SQLITE_CORRUPT_BKPT; |
︙ | ︙ | |||
1027 1028 1029 1030 1031 1032 1033 | pPage->nFree = pBt->usableSize - first; decodeFlags(pPage, flags); pPage->hdrOffset = hdr; pPage->cellOffset = first; pPage->nOverflow = 0; assert( pBt->pageSize>=512 && pBt->pageSize<=32768 ); pPage->maskPage = pBt->pageSize - 1; | < | 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 | pPage->nFree = pBt->usableSize - first; decodeFlags(pPage, flags); pPage->hdrOffset = hdr; pPage->cellOffset = first; pPage->nOverflow = 0; assert( pBt->pageSize>=512 && pBt->pageSize<=32768 ); pPage->maskPage = pBt->pageSize - 1; pPage->nCell = 0; pPage->isInit = 1; } /* ** Convert a DbPage obtained from the pager into a MemPage used by |
︙ | ︙ | |||
3439 3440 3441 3442 3443 3444 3445 | assert( pCur->eState==CURSOR_VALID ); assert( pCur->iPage<BTCURSOR_MAX_DEPTH ); if( pCur->iPage>=(BTCURSOR_MAX_DEPTH-1) ){ return SQLITE_CORRUPT_BKPT; } rc = getAndInitPage(pBt, newPgno, &pNewPage); if( rc ) return rc; | < > > > > > > > > > > > > > > > > > > > > | > > > > < | 3437 3438 3439 3440 3441 3442 3443 3444 3445 3446 3447 3448 3449 3450 3451 3452 3453 3454 3455 3456 3457 3458 3459 3460 3461 3462 3463 3464 3465 3466 3467 3468 3469 3470 3471 3472 3473 3474 3475 3476 3477 3478 3479 3480 3481 3482 3483 3484 3485 3486 3487 3488 3489 3490 3491 3492 3493 3494 3495 3496 3497 3498 3499 3500 3501 3502 3503 3504 | assert( pCur->eState==CURSOR_VALID ); assert( pCur->iPage<BTCURSOR_MAX_DEPTH ); if( pCur->iPage>=(BTCURSOR_MAX_DEPTH-1) ){ return SQLITE_CORRUPT_BKPT; } rc = getAndInitPage(pBt, newPgno, &pNewPage); if( rc ) return rc; pCur->apPage[i+1] = pNewPage; pCur->aiIdx[i+1] = 0; pCur->iPage++; pCur->info.nSize = 0; pCur->validNKey = 0; if( pNewPage->nCell<1 ){ return SQLITE_CORRUPT_BKPT; } return SQLITE_OK; } #ifndef NDEBUG /* ** Page pParent is an internal (non-leaf) tree page. This function ** asserts that page number iChild is the left-child if the iIdx'th ** cell in page pParent. Or, if iIdx is equal to the total number of ** cells in pParent, that page number iChild is the right-child of ** the page. */ static void assertParentIndex(MemPage *pParent, int iIdx, Pgno iChild){ assert( iIdx<=pParent->nCell ); if( iIdx==pParent->nCell ){ assert( get4byte(&pParent->aData[pParent->hdrOffset+8])==iChild ); }else{ assert( get4byte(findCell(pParent, iIdx))==iChild ); } } #else # define assertParentIndex(x,y,z) #endif /* ** Move the cursor up to the parent page. ** ** pCur->idx is set to the cell index that contains the pointer ** to the page we are coming from. If we are coming from the ** right-most child page then pCur->idx is set to one more than ** the largest cell index. */ void sqlite3BtreeMoveToParent(BtCursor *pCur){ assert( cursorHoldsMutex(pCur) ); assert( pCur->eState==CURSOR_VALID ); assert( pCur->iPage>0 ); assert( pCur->apPage[pCur->iPage] ); assertParentIndex( pCur->apPage[pCur->iPage-1], pCur->aiIdx[pCur->iPage-1], pCur->apPage[pCur->iPage]->pgno ); releasePage(pCur->apPage[pCur->iPage]); pCur->iPage--; pCur->info.nSize = 0; pCur->validNKey = 0; } /* ** Move the cursor to the root page */ static int moveToRoot(BtCursor *pCur){ MemPage *pRoot; |
︙ | ︙ | |||
4585 4586 4587 4588 4589 4590 4591 | for(i=0; i<pPage->nCell; i++){ u8 *pCell = findCell(pPage, i); rc = reparentPage(pBt, get4byte(pCell), pPage, i, updatePtrmap); if( rc!=SQLITE_OK ) return rc; } rc = reparentPage(pBt, iRight, pPage, i, updatePtrmap); | < | 4605 4606 4607 4608 4609 4610 4611 4612 4613 4614 4615 4616 4617 4618 | for(i=0; i<pPage->nCell; i++){ u8 *pCell = findCell(pPage, i); rc = reparentPage(pBt, get4byte(pCell), pPage, i, updatePtrmap); if( rc!=SQLITE_OK ) return rc; } rc = reparentPage(pBt, iRight, pPage, i, updatePtrmap); } return rc; } /* ** Remove the i-th cell from pPage. This routine effects pPage only. ** The cell content is not freed or deallocated. It is assumed that |
︙ | ︙ | |||
4620 4621 4622 4623 4624 4625 4626 | for(i=idx+1; i<pPage->nCell; i++, ptr+=2){ ptr[0] = ptr[2]; ptr[1] = ptr[3]; } pPage->nCell--; put2byte(&data[pPage->hdrOffset+3], pPage->nCell); pPage->nFree += 2; | < | 4639 4640 4641 4642 4643 4644 4645 4646 4647 4648 4649 4650 4651 4652 | for(i=idx+1; i<pPage->nCell; i++, ptr+=2){ ptr[0] = ptr[2]; ptr[1] = ptr[3]; } pPage->nCell--; put2byte(&data[pPage->hdrOffset+3], pPage->nCell); pPage->nFree += 2; } /* ** Insert a new cell on pPage at cell index "i". pCell points to the ** content of the cell. ** ** If the cell content will fit on the page, then put it there. If it |
︙ | ︙ | |||
4700 4701 4702 4703 4704 4705 4706 | memcpy(&data[idx+nSkip], pCell+nSkip, sz-nSkip); for(j=end-2, ptr=&data[j]; j>ins; j-=2, ptr-=2){ ptr[0] = ptr[-2]; ptr[1] = ptr[-1]; } put2byte(&data[ins], idx); put2byte(&data[hdr+3], pPage->nCell); | < | 4718 4719 4720 4721 4722 4723 4724 4725 4726 4727 4728 4729 4730 4731 | memcpy(&data[idx+nSkip], pCell+nSkip, sz-nSkip); for(j=end-2, ptr=&data[j]; j>ins; j-=2, ptr-=2){ ptr[0] = ptr[-2]; ptr[1] = ptr[-1]; } put2byte(&data[ins], idx); put2byte(&data[hdr+3], pPage->nCell); #ifndef SQLITE_OMIT_AUTOVACUUM if( pPage->pBt->autoVacuum ){ /* The cell may contain a pointer to an overflow page. If so, write ** the entry for the overflow page into the pointer map. */ CellInfo info; sqlite3BtreeParseCellPtr(pPage, pCell, &info); |
︙ | ︙ | |||
4829 4830 4831 4832 4833 4834 4835 | if( rc==SQLITE_OK ){ pCell = pPage->aOvfl[0].pCell; szCell = cellSizePtr(pPage, pCell); zeroPage(pNew, pPage->aData[0]); assemblePage(pNew, 1, &pCell, &szCell); pPage->nOverflow = 0; | < < < < < < | 4846 4847 4848 4849 4850 4851 4852 4853 4854 4855 4856 4857 4858 4859 | if( rc==SQLITE_OK ){ 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. ** ** Ignore the return value of the call to fillInCell(). fillInCell() ** may only return other than SQLITE_OK if it is required to allocate ** one or more overflow pages. Since an internal table B-Tree cell |
︙ | ︙ | |||
5019 5020 5021 5022 5023 5024 5025 | } /* ** 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 */ | < < < < < < < < < < < < | < > < | 5030 5031 5032 5033 5034 5035 5036 5037 5038 5039 5040 5041 5042 5043 5044 5045 5046 5047 5048 5049 5050 5051 | } /* ** 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 */ idx = pCur->aiIdx[pCur->iPage-1]; assertParentIndex(pParent, idx, pPage->pgno); /* ** Initialize variables so that it will be safe to jump ** directly to balance_cleanup at any moment. */ nOld = nNew = 0; /* ** Find sibling pages to pPage and the cells in pParent that divide ** the siblings. An attempt is made to find NN siblings on either ** side of pPage. More siblings are taken from one side, however, if ** pPage there are fewer than NN siblings on the other side. If pParent ** has NB or fewer children then all children of pParent are taken. |
︙ | ︙ | |||
5728 5729 5730 5731 5732 5733 5734 5735 5736 5737 5738 5739 5740 5741 | } } } if( rc==SQLITE_OK ){ pCur->iPage++; pCur->apPage[1] = pChild; rc = balance_nonroot(pCur); }else{ releasePage(pChild); } return rc; } | > | 5726 5727 5728 5729 5730 5731 5732 5733 5734 5735 5736 5737 5738 5739 5740 | } } } if( rc==SQLITE_OK ){ pCur->iPage++; pCur->apPage[1] = pChild; pCur->aiIdx[0] = 0; rc = balance_nonroot(pCur); }else{ releasePage(pChild); } return rc; } |
︙ | ︙ |
Changes to src/btreeInt.h.
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: btreeInt.h,v 1.33 2008/09/29 15:53:26 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. |
︙ | ︙ | |||
267 268 269 270 271 272 273 | ** The pageDestructor() routine handles that chore. ** ** Access to all fields of this structure is controlled by the mutex ** stored in MemPage.pBt->mutex. */ struct MemPage { u8 isInit; /* True if previously initialized. MUST BE FIRST! */ | < | 267 268 269 270 271 272 273 274 275 276 277 278 279 280 | ** The pageDestructor() routine handles that chore. ** ** Access to all fields of this structure is controlled by the mutex ** stored in MemPage.pBt->mutex. */ struct MemPage { u8 isInit; /* True if previously initialized. MUST BE FIRST! */ u8 nOverflow; /* Number of overflow cell bodies in aCell[] */ u8 intKey; /* True if intkey flag is set */ u8 leaf; /* True if leaf flag is set */ u8 hasData; /* True if this page stores data */ u8 hdrOffset; /* 100 for page 1. 0 otherwise */ u8 childPtrSize; /* 0 if leaf==1. 4 if leaf==0 */ u16 maxLocal; /* Copy of BtShared.maxLocal or BtShared.maxLeaf */ |
︙ | ︙ |