Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Simplifications to btree.c in support of structural testing. Renamed the "skip" field of the BtCursor object to "skipNext" to make it easier to search for places where it is used. (CVS 6896) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
d3897235d77e48ad09f7edb0a7641458 |
User & Date: | drh 2009-07-15 17:25:46.000 |
Context
2009-07-15
| ||
18:15 | Fix a potential database corruption following DROP TABLE when the pending byte page corresponds to a ptrmap page. This situation cannot happen in a real deployment - but it still needs to be fixed. (CVS 6897) (check-in: 6242db39f7 user: drh tags: trunk) | |
17:25 | Simplifications to btree.c in support of structural testing. Renamed the "skip" field of the BtCursor object to "skipNext" to make it easier to search for places where it is used. (CVS 6896) (check-in: d3897235d7 user: drh tags: trunk) | |
16:30 | Remove an assert() from vdbeaux.c that might not be true if the database file is corrupt. (CVS 6895) (check-in: a42dc51e3b 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.689 2009/07/15 17:25:46 drh 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" |
︙ | ︙ | |||
496 497 498 499 500 501 502 | ** optimization 2 above is ommitted if the corresponding bit is already ** set in BtShared.pHasContent. The contents of the bitvec are cleared ** at the end of every transaction. */ static int btreeSetHasContent(BtShared *pBt, Pgno pgno){ int rc = SQLITE_OK; if( !pBt->pHasContent ){ | | | | > | | | < | 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 | ** optimization 2 above is ommitted if the corresponding bit is already ** set in BtShared.pHasContent. The contents of the bitvec are cleared ** at the end of every transaction. */ static int btreeSetHasContent(BtShared *pBt, Pgno pgno){ int rc = SQLITE_OK; if( !pBt->pHasContent ){ int nPage = 100; sqlite3PagerPagecount(pBt->pPager, &nPage); /* If sqlite3PagerPagecount() fails there is no harm because the ** nPage variable is unchanged from its default value of 100 */ pBt->pHasContent = sqlite3BitvecCreate((u32)nPage); if( !pBt->pHasContent ){ rc = SQLITE_NOMEM; } } if( rc==SQLITE_OK && pgno<=sqlite3BitvecSize(pBt->pHasContent) ){ rc = sqlite3BitvecSet(pBt->pHasContent, pgno); } return rc; } |
︙ | ︙ | |||
544 545 546 547 548 549 550 551 552 553 554 555 556 557 | int rc; assert( CURSOR_VALID==pCur->eState ); assert( 0==pCur->pKey ); assert( cursorHoldsMutex(pCur) ); rc = sqlite3BtreeKeySize(pCur, &pCur->nKey); /* If this is an intKey table, then the above call to BtreeKeySize() ** stores the integer key in pCur->nKey. In this case this value is ** all that is required. Otherwise, if pCur is not open on an intKey ** table, then malloc space for and store the pCur->nKey bytes of key ** data. */ | > | | 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 | int rc; assert( CURSOR_VALID==pCur->eState ); assert( 0==pCur->pKey ); assert( cursorHoldsMutex(pCur) ); rc = sqlite3BtreeKeySize(pCur, &pCur->nKey); assert( rc==SQLITE_OK ); /* Cannot fail since pCur->eState==VALID */ /* If this is an intKey table, then the above call to BtreeKeySize() ** stores the integer key in pCur->nKey. In this case this value is ** all that is required. Otherwise, if pCur is not open on an intKey ** table, then malloc space for and store the pCur->nKey bytes of key ** data. */ if( 0==pCur->apPage[0]->intKey ){ void *pKey = sqlite3Malloc( (int)pCur->nKey ); if( pKey ){ rc = sqlite3BtreeKey(pCur, 0, (int)pCur->nKey, pKey); if( rc==SQLITE_OK ){ pCur->pKey = pKey; }else{ sqlite3_free(pKey); |
︙ | ︙ | |||
654 655 656 657 658 659 660 | ** saveCursorPosition(). */ static int btreeRestoreCursorPosition(BtCursor *pCur){ int rc; assert( cursorHoldsMutex(pCur) ); assert( pCur->eState>=CURSOR_REQUIRESEEK ); if( pCur->eState==CURSOR_FAULT ){ | | | | 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 | ** saveCursorPosition(). */ static int btreeRestoreCursorPosition(BtCursor *pCur){ int rc; assert( cursorHoldsMutex(pCur) ); assert( pCur->eState>=CURSOR_REQUIRESEEK ); if( pCur->eState==CURSOR_FAULT ){ return pCur->skipNext; } pCur->eState = CURSOR_INVALID; rc = btreeMoveto(pCur, pCur->pKey, pCur->nKey, 0, &pCur->skipNext); if( rc==SQLITE_OK ){ sqlite3_free(pCur->pKey); pCur->pKey = 0; assert( pCur->eState==CURSOR_VALID || pCur->eState==CURSOR_INVALID ); } return rc; } |
︙ | ︙ | |||
687 688 689 690 691 692 693 | int rc; rc = restoreCursorPosition(pCur); if( rc ){ *pHasMoved = 1; return rc; } | | | 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 | int rc; rc = restoreCursorPosition(pCur); if( rc ){ *pHasMoved = 1; return rc; } if( pCur->eState!=CURSOR_VALID || pCur->skipNext!=0 ){ *pHasMoved = 1; }else{ *pHasMoved = 0; } return SQLITE_OK; } |
︙ | ︙ | |||
2429 2430 2431 2432 2433 2434 2435 | goto trans_begun; } #endif /* Any read-only or read-write transaction implies a read-lock on ** page 1. So if some other shared-cache client already has a write-lock ** on page 1, the transaction cannot be opened. */ | | | < | 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 | goto trans_begun; } #endif /* Any read-only or read-write transaction implies a read-lock on ** page 1. So if some other shared-cache client already has a write-lock ** on page 1, the transaction cannot be opened. */ rc = querySharedCacheTableLock(p, MASTER_ROOT, READ_LOCK); if( SQLITE_OK!=rc ) goto trans_begun; do { /* Call lockBtree() until either pBt->pPage1 is populated or ** lockBtree() returns something other than SQLITE_OK. lockBtree() ** may return SQLITE_OK but leave pBt->pPage1 set to 0 if after ** reading page 1 it discovers that the page-size of the database ** file is not pBt->pageSize. In this case lockBtree() will update |
︙ | ︙ | |||
3087 3088 3089 3090 3091 3092 3093 | void sqlite3BtreeTripAllCursors(Btree *pBtree, int errCode){ BtCursor *p; sqlite3BtreeEnter(pBtree); for(p=pBtree->pBt->pCursor; p; p=p->pNext){ int i; sqlite3BtreeClearCursor(p); p->eState = CURSOR_FAULT; | | | 3087 3088 3089 3090 3091 3092 3093 3094 3095 3096 3097 3098 3099 3100 3101 | void sqlite3BtreeTripAllCursors(Btree *pBtree, int errCode){ BtCursor *p; sqlite3BtreeEnter(pBtree); for(p=pBtree->pBt->pCursor; p; p=p->pNext){ int i; sqlite3BtreeClearCursor(p); p->eState = CURSOR_FAULT; p->skipNext = errCode; for(i=0; i<=p->iPage; i++){ releasePage(p->apPage[i]); p->apPage[i] = 0; } } sqlite3BtreeLeave(pBtree); } |
︙ | ︙ | |||
4007 4008 4009 4010 4011 4012 4013 | assert( cursorHoldsMutex(pCur) ); assert( CURSOR_INVALID < CURSOR_REQUIRESEEK ); assert( CURSOR_VALID < CURSOR_REQUIRESEEK ); assert( CURSOR_FAULT > CURSOR_REQUIRESEEK ); if( pCur->eState>=CURSOR_REQUIRESEEK ){ if( pCur->eState==CURSOR_FAULT ){ | | | < | | | 4007 4008 4009 4010 4011 4012 4013 4014 4015 4016 4017 4018 4019 4020 4021 4022 4023 4024 4025 4026 4027 4028 4029 4030 4031 4032 4033 4034 4035 | assert( cursorHoldsMutex(pCur) ); assert( CURSOR_INVALID < CURSOR_REQUIRESEEK ); assert( CURSOR_VALID < CURSOR_REQUIRESEEK ); assert( CURSOR_FAULT > CURSOR_REQUIRESEEK ); if( pCur->eState>=CURSOR_REQUIRESEEK ){ if( pCur->eState==CURSOR_FAULT ){ assert( pCur->skipNext!=SQLITE_OK ); return pCur->skipNext; } sqlite3BtreeClearCursor(pCur); } if( pCur->iPage>=0 ){ int i; for(i=1; i<=pCur->iPage; i++){ releasePage(pCur->apPage[i]); } pCur->iPage = 0; }else{ rc = getAndInitPage(pBt, pCur->pgnoRoot, &pCur->apPage[0]); if( rc!=SQLITE_OK ){ pCur->eState = CURSOR_INVALID; return rc; } pCur->iPage = 0; /* If pCur->pKeyInfo is not NULL, then the caller that opened this cursor ** expected to open it on an index b-tree. Otherwise, if pKeyInfo is |
︙ | ︙ | |||
4419 4420 4421 4422 4423 4424 4425 | return rc; } assert( pRes!=0 ); if( CURSOR_INVALID==pCur->eState ){ *pRes = 1; return SQLITE_OK; } | | | | | 4418 4419 4420 4421 4422 4423 4424 4425 4426 4427 4428 4429 4430 4431 4432 4433 4434 4435 4436 4437 | return rc; } assert( pRes!=0 ); if( CURSOR_INVALID==pCur->eState ){ *pRes = 1; return SQLITE_OK; } if( pCur->skipNext>0 ){ pCur->skipNext = 0; *pRes = 0; return SQLITE_OK; } pCur->skipNext = 0; pPage = pCur->apPage[pCur->iPage]; idx = ++pCur->aiIdx[pCur->iPage]; assert( pPage->isInit ); assert( idx<=pPage->nCell ); pCur->info.nSize = 0; |
︙ | ︙ | |||
4487 4488 4489 4490 4491 4492 4493 | return rc; } pCur->atLast = 0; if( CURSOR_INVALID==pCur->eState ){ *pRes = 1; return SQLITE_OK; } | | | | | 4486 4487 4488 4489 4490 4491 4492 4493 4494 4495 4496 4497 4498 4499 4500 4501 4502 4503 4504 4505 | return rc; } pCur->atLast = 0; if( CURSOR_INVALID==pCur->eState ){ *pRes = 1; return SQLITE_OK; } if( pCur->skipNext<0 ){ pCur->skipNext = 0; *pRes = 0; return SQLITE_OK; } pCur->skipNext = 0; pPage = pCur->apPage[pCur->iPage]; assert( pPage->isInit ); if( !pPage->leaf ){ int idx = pCur->aiIdx[pCur->iPage]; rc = moveToChild(pCur, get4byte(findCell(pPage, idx))); if( rc ){ |
︙ | ︙ | |||
4624 4625 4626 4627 4628 4629 4630 | } if( rc ){ pTrunk = 0; goto end_allocate_page; } k = get4byte(&pTrunk->aData[4]); | < | 4623 4624 4625 4626 4627 4628 4629 4630 4631 4632 4633 4634 4635 4636 | } if( rc ){ pTrunk = 0; goto end_allocate_page; } k = get4byte(&pTrunk->aData[4]); if( k==0 && !searchList ){ /* The trunk has no leaves and the list is not being searched. ** So extract the trunk page itself and use it as the newly ** allocated page */ assert( pPrevTrunk==0 ); rc = sqlite3PagerWrite(pTrunk->pDbPage); if( rc ){ |
︙ | ︙ | |||
5183 5184 5185 5186 5187 5188 5189 | assert( idx>=0 && idx<pPage->nCell ); assert( sz==cellSize(pPage, idx) ); assert( sqlite3PagerIswriteable(pPage->pDbPage) ); assert( sqlite3_mutex_held(pPage->pBt->mutex) ); data = pPage->aData; ptr = &data[pPage->cellOffset + 2*idx]; pc = get2byte(ptr); | | | 5181 5182 5183 5184 5185 5186 5187 5188 5189 5190 5191 5192 5193 5194 5195 | assert( idx>=0 && idx<pPage->nCell ); assert( sz==cellSize(pPage, idx) ); assert( sqlite3PagerIswriteable(pPage->pDbPage) ); assert( sqlite3_mutex_held(pPage->pBt->mutex) ); data = pPage->aData; ptr = &data[pPage->cellOffset + 2*idx]; pc = get2byte(ptr); if( (pc<pPage->hdrOffset+6+pPage->childPtrSize) || (pc+sz>pPage->pBt->usableSize) ){ return SQLITE_CORRUPT_BKPT; } rc = freeSpace(pPage, pc, sz); if( rc!=SQLITE_OK ){ return rc; } |
︙ | ︙ | |||
6426 6427 6428 6429 6430 6431 6432 | ** cursors open on the row being replaced (assuming this is a replace ** operation - if it is not, the following is a no-op). */ if( pCur->pKeyInfo==0 ){ invalidateIncrblobCursors(p, pCur->pgnoRoot, nKey, 0); } if( pCur->eState==CURSOR_FAULT ){ | | | < | > > | < | | 6424 6425 6426 6427 6428 6429 6430 6431 6432 6433 6434 6435 6436 6437 6438 6439 6440 6441 6442 6443 6444 6445 6446 6447 6448 6449 6450 6451 6452 6453 6454 6455 6456 6457 | ** cursors open on the row being replaced (assuming this is a replace ** operation - if it is not, the following is a no-op). */ if( pCur->pKeyInfo==0 ){ invalidateIncrblobCursors(p, pCur->pgnoRoot, nKey, 0); } if( pCur->eState==CURSOR_FAULT ){ assert( pCur->skipNext!=SQLITE_OK ); return pCur->skipNext; } /* Save the positions of any other cursors open on this table. ** ** In some cases, the call to btreeMoveto() below is a no-op. For ** example, when inserting data into a table with auto-generated integer ** keys, the VDBE layer invokes sqlite3BtreeLast() to figure out the ** integer key to use. It then calls this function to actually insert the ** data into the intkey B-Tree. In this case btreeMoveto() recognizes ** that the cursor is already where it needs to be and returns without ** doing any work. To avoid thwarting these optimizations, it is important ** not to clear the cursor here. */ rc = saveAllCursors(pBt, pCur->pgnoRoot, pCur); if( rc ) return rc; if( !loc ){ rc = btreeMoveto(pCur, pKey, nKey, appendBias, &loc); if( rc ) return rc; } assert( pCur->eState==CURSOR_VALID || (pCur->eState==CURSOR_INVALID && loc) ); pPage = pCur->apPage[pCur->iPage]; assert( pPage->intKey || nKey>=0 ); assert( pPage->leaf || !pPage->intKey ); |
︙ | ︙ | |||
6576 6577 6578 6579 6580 6581 6582 | ** the entry being deleted. This cell will replace the cell being deleted ** from the internal node. The 'previous' entry is used for this instead ** of the 'next' entry, as the previous entry is always a part of the ** sub-tree headed by the child page of the cell being deleted. This makes ** balancing the tree following the delete operation easier. */ if( !pPage->leaf ){ int notUsed; | | | < | 6574 6575 6576 6577 6578 6579 6580 6581 6582 6583 6584 6585 6586 6587 6588 6589 | ** the entry being deleted. This cell will replace the cell being deleted ** from the internal node. The 'previous' entry is used for this instead ** of the 'next' entry, as the previous entry is always a part of the ** sub-tree headed by the child page of the cell being deleted. This makes ** balancing the tree following the delete operation easier. */ if( !pPage->leaf ){ int notUsed; rc = sqlite3BtreePrevious(pCur, ¬Used); if( rc ) return rc; } /* Save the positions of any other cursors open on this table before ** making any modifications. Make the page containing the entry to be ** deleted writable. Then free any overflow pages associated with the ** entry and finally remove the cell itself from within the page. */ |
︙ | ︙ |
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.52 2009/07/15 17:25:46 drh 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. |
︙ | ︙ | |||
488 489 490 491 492 493 494 | CellInfo info; /* A parse of the cell we are pointing at */ u8 wrFlag; /* True if writable */ u8 atLast; /* Cursor pointing to the last entry */ u8 validNKey; /* True if info.nKey is valid */ u8 eState; /* One of the CURSOR_XXX constants (see below) */ void *pKey; /* Saved key that was cursor's last known position */ i64 nKey; /* Size of pKey, or last integer key */ | | | 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 | CellInfo info; /* A parse of the cell we are pointing at */ u8 wrFlag; /* True if writable */ u8 atLast; /* Cursor pointing to the last entry */ u8 validNKey; /* True if info.nKey is valid */ u8 eState; /* One of the CURSOR_XXX constants (see below) */ void *pKey; /* Saved key that was cursor's last known position */ i64 nKey; /* Size of pKey, or last integer key */ int skipNext; /* Prev() is noop if negative. Next() is noop if positive */ #ifndef SQLITE_OMIT_INCRBLOB u8 isIncrblobHandle; /* True if this cursor is an incr. io handle */ Pgno *aOverflow; /* Cache of overflow page locations */ #endif i16 iPage; /* Index of current page in apPage */ MemPage *apPage[BTCURSOR_MAX_DEPTH]; /* Pages from root to current page */ u16 aiIdx[BTCURSOR_MAX_DEPTH]; /* Current index in apPage[i] */ |
︙ | ︙ | |||
634 635 636 637 638 639 640 | /* ** Read or write a two- and four-byte big-endian integer values. */ #define get2byte(x) ((x)[0]<<8 | (x)[1]) #define put2byte(p,v) ((p)[0] = (u8)((v)>>8), (p)[1] = (u8)(v)) #define get4byte sqlite3Get4byte #define put4byte sqlite3Put4byte | < | 634 635 636 637 638 639 640 | /* ** Read or write a two- and four-byte big-endian integer values. */ #define get2byte(x) ((x)[0]<<8 | (x)[1]) #define put2byte(p,v) ((p)[0] = (u8)((v)>>8), (p)[1] = (u8)(v)) #define get4byte sqlite3Get4byte #define put4byte sqlite3Put4byte |