Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Fix a recently introduced problem with deleting entries from index tables. (CVS 5754) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
83c064cae481ca95b7107e22e98fc599 |
User & Date: | danielk1977 2008-09-30 09:31:45.000 |
Context
2008-09-30
| ||
14:06 | Change leading tabs into spaces. (CVS 5755) (check-in: 4e536463c1 user: drh tags: trunk) | |
09:31 | Fix a recently introduced problem with deleting entries from index tables. (CVS 5754) (check-in: 83c064cae4 user: danielk1977 tags: trunk) | |
04:20 | Misc clean up. Wrapped a CE only variable in if-defs. Changed to only provide cache hint for CE builds (as this prevents CE from compressing the file.) Performance testing on XP and Vista showed caching hint had little effect when the DB size was much smaller than the O/S disk cache size, and provided only marginal benefit when the DB size was much larger than the cache. On Vista, overall system performance was hurt for very large DBs. Ticket #3387. (CVS 5753) (check-in: 15dd0169a4 user: shane 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.521 2008/09/30 09:31:45 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" |
︙ | ︙ | |||
5879 5880 5881 5882 5883 5884 5885 | ** do something we will leave a hole on an internal page. ** We have to fill the hole by moving in a cell from a leaf. The ** next Cell after the one to be deleted is guaranteed to exist and ** to be a leaf so we can use it. */ BtCursor leafCur; MemPage *pLeafPage; | < > < > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | > > > > > > > > | | 5879 5880 5881 5882 5883 5884 5885 5886 5887 5888 5889 5890 5891 5892 5893 5894 5895 5896 5897 5898 5899 5900 5901 5902 5903 5904 5905 5906 5907 5908 5909 5910 5911 5912 5913 5914 5915 5916 5917 5918 5919 5920 5921 5922 5923 5924 5925 5926 5927 5928 5929 5930 5931 5932 5933 5934 5935 5936 5937 5938 5939 5940 5941 5942 5943 5944 5945 5946 5947 5948 5949 5950 5951 5952 5953 5954 5955 5956 5957 5958 5959 5960 5961 5962 5963 5964 5965 5966 5967 5968 5969 5970 5971 5972 5973 5974 5975 5976 5977 5978 5979 5980 5981 | ** do something we will leave a hole on an internal page. ** We have to fill the hole by moving in a cell from a leaf. The ** next Cell after the one to be deleted is guaranteed to exist and ** to be a leaf so we can use it. */ BtCursor leafCur; MemPage *pLeafPage; unsigned char *pNext; int notUsed; unsigned char *tempCell = 0; assert( !pPage->intKey ); sqlite3BtreeGetTempCursor(pCur, &leafCur); rc = sqlite3BtreeNext(&leafCur, ¬Used); if( rc==SQLITE_OK ){ assert( leafCur.aiIdx[leafCur.iPage]==0 ); pLeafPage = leafCur.apPage[leafCur.iPage]; rc = sqlite3PagerWrite(pLeafPage->pDbPage); } if( rc==SQLITE_OK ){ int leafCursorInvalid = 0; u16 szNext; TRACE(("DELETE: table=%d delete internal from %d replace from leaf %d\n", pCur->pgnoRoot, pPage->pgno, pLeafPage->pgno)); dropCell(pPage, idx, cellSizePtr(pPage, pCell)); pNext = findCell(pLeafPage, 0); szNext = cellSizePtr(pLeafPage, pNext); assert( MX_CELL_SIZE(pBt)>=szNext+4 ); allocateTempSpace(pBt); tempCell = pBt->pTmpSpace; if( tempCell==0 ){ rc = SQLITE_NOMEM; } if( rc==SQLITE_OK ){ rc = insertCell(pPage, idx, pNext-4, szNext+4, tempCell, 0); } if( (pPage->nOverflow>0 || (pPage->nFree > pBt->usableSize*2/3)) && (pLeafPage->nFree+2+szNext > pBt->usableSize*2/3) ){ /* This branch is taken if the internal node is now either over or ** underfull and the leaf node will be underfull after the just cell ** copied to the internal node is deleted from it. This is a special ** case because the call to balance() to correct the internal node ** may change the tree structure and invalidate the contents of ** the leafCur.apPage[] and leafCur.aiIdx[] arrays, which will be ** used by the balance() required to correct the underfull leaf ** node. ** ** The formula used in the expression above are based on facets of ** the SQLite file-format that do not change over time. */ leafCursorInvalid = 1; } if( rc==SQLITE_OK ){ put4byte(findOverflowCell(pPage, idx), pgnoChild); rc = balance(pCur, 0); } if( rc==SQLITE_OK && leafCursorInvalid ){ /* The leaf-node is now underfull and so the tree needs to be ** rebalanced. However, the balance() operation on the internal ** node above may have modified the structure of the B-Tree and ** so the current contents of leafCur.apPage[] and leafCur.aiIdx[] ** may not be trusted. ** ** It is not possible to copy the ancestry from pCur, as the same ** balance() call has invalidated the pCur->apPage[] and aiIdx[] ** arrays. ** ** The call to saveCursorPosition() below internally saves the ** key that leafCur is currently pointing to. Currently, there ** are two copies of that key in the tree - one here on the leaf ** page and one on some internal node in the tree. The copy on ** the leaf node is always the next key in tree-order after the ** copy on the internal node. So, the call to sqlite3BtreeNext() ** calls restoreCursorPosition() to point the cursor to the copy ** stored on the internal node, then advances to the next entry, ** which happens to be the copy of the key on the internal node. ** Net effect: leafCur is pointing back where */ #ifndef NDEBUG Pgno leafPgno = pLeafPage->pgno; #endif rc = saveCursorPosition(&leafCur); if( rc==SQLITE_OK ){ rc = sqlite3BtreeNext(&leafCur, ¬Used); } pLeafPage = leafCur.apPage[leafCur.iPage]; assert( pLeafPage->pgno==leafPgno ); assert( leafCur.aiIdx[leafCur.iPage]==0 ); } if( rc==SQLITE_OK ){ dropCell(pLeafPage, 0, szNext); rc = balance(&leafCur, 0); } } sqlite3BtreeReleaseTempCursor(&leafCur); }else{ TRACE(("DELETE: table=%d delete from leaf %d\n", pCur->pgnoRoot, pPage->pgno)); |
︙ | ︙ | |||
7022 7023 7024 7025 7026 7027 7028 | nCopy = nToPageSize; }else{ zTo += (((iFrom-1)*nFromPageSize) - (i-1)*nToPageSize); nCopy = nFromPageSize; } memcpy(zTo, zFrom, nCopy); | | | 7076 7077 7078 7079 7080 7081 7082 7083 7084 7085 7086 7087 7088 7089 7090 | nCopy = nToPageSize; }else{ zTo += (((iFrom-1)*nFromPageSize) - (i-1)*nToPageSize); nCopy = nFromPageSize; } memcpy(zTo, zFrom, nCopy); sqlite3PagerUnref(pFromPage); } } if( pToPage ){ MemPage *p = (MemPage *)sqlite3PagerGetExtra(pToPage); p->isInit = 0; sqlite3PagerUnref(pToPage); |
︙ | ︙ |