Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Fixes to the overflow-chain optization of (3672). (CVS 3674) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
d6986d1e7cba1d114fa06c5560ffc6bb |
User & Date: | drh 2007-03-06 15:53:44.000 |
Context
2007-03-06
| ||
16:03 | Catch an out-of-memory condition in vacuum code. (Bug in (3373)). (CVS 3675) (check-in: 302ec76857 user: danielk1977 tags: trunk) | |
15:53 | Fixes to the overflow-chain optization of (3672). (CVS 3674) (check-in: d6986d1e7c user: drh tags: trunk) | |
13:46 | Use heap instead of stack for large buffers in the pager. Fix for #2262. (CVS 3673) (check-in: dfe1dffa45 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.338 2007/03/06 15:53:44 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. |
︙ | ︙ | |||
361 362 363 364 365 366 367 368 369 370 371 372 373 374 | ** based on information extract from the raw disk page. */ typedef struct CellInfo CellInfo; struct CellInfo { u8 *pCell; /* Pointer to the start of cell content */ i64 nKey; /* The key for INTKEY tables, or number of bytes in key */ u32 nData; /* Number of bytes of data */ u16 nHeader; /* Size of the cell content header in bytes */ u16 nLocal; /* Amount of payload held locally */ u16 iOverflow; /* Offset to overflow page number. Zero if no overflow */ u16 nSize; /* Size of the cell content on the main b-tree page */ }; /* | > | 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 | ** based on information extract from the raw disk page. */ typedef struct CellInfo CellInfo; struct CellInfo { u8 *pCell; /* Pointer to the start of cell content */ i64 nKey; /* The key for INTKEY tables, or number of bytes in key */ u32 nData; /* Number of bytes of data */ u32 nPayload; /* Total amount of payload */ u16 nHeader; /* Size of the cell content header in bytes */ u16 nLocal; /* Amount of payload held locally */ u16 iOverflow; /* Offset to overflow page number. Zero if no overflow */ u16 nSize; /* Size of the cell content on the main b-tree page */ }; /* |
︙ | ︙ | |||
940 941 942 943 944 945 946 947 948 949 950 951 952 953 | n += getVarint(&pCell[n], (u64 *)&pInfo->nKey); }else{ u32 x; n += getVarint32(&pCell[n], &x); pInfo->nKey = x; nPayload += x; } pInfo->nHeader = n; if( nPayload<=pPage->maxLocal ){ /* This is the (easy) common case where the entire payload fits ** on the local page. No overflow is required. */ int nSize; /* Total size of cell content in bytes */ pInfo->nLocal = nPayload; | > | 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 | n += getVarint(&pCell[n], (u64 *)&pInfo->nKey); }else{ u32 x; n += getVarint32(&pCell[n], &x); pInfo->nKey = x; nPayload += x; } pInfo->nPayload = nPayload; pInfo->nHeader = n; if( nPayload<=pPage->maxLocal ){ /* This is the (easy) common case where the entire payload fits ** on the local page. No overflow is required. */ int nSize; /* Total size of cell content in bytes */ pInfo->nLocal = nPayload; |
︙ | ︙ | |||
1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 | ** to an overflow page, insert an entry into the pointer-map ** for the overflow page. */ static int ptrmapPutOvflPtr(MemPage *pPage, u8 *pCell){ if( pCell ){ CellInfo info; parseCellPtr(pPage, pCell, &info); if( (info.nData+(pPage->intKey?0:info.nKey))>info.nLocal ){ Pgno ovfl = get4byte(&pCell[info.iOverflow]); return ptrmapPut(pPage->pBt, ovfl, PTRMAP_OVERFLOW1, pPage->pgno); } } return SQLITE_OK; } | > | 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 | ** to an overflow page, insert an entry into the pointer-map ** for the overflow page. */ static int ptrmapPutOvflPtr(MemPage *pPage, u8 *pCell){ if( pCell ){ CellInfo info; parseCellPtr(pPage, pCell, &info); assert( (info.nData+(pPage->intKey?0:info.nKey))==info.nPayload ); if( (info.nData+(pPage->intKey?0:info.nKey))>info.nLocal ){ Pgno ovfl = get4byte(&pCell[info.iOverflow]); return ptrmapPut(pPage->pBt, ovfl, PTRMAP_OVERFLOW1, pPage->pgno); } } return SQLITE_OK; } |
︙ | ︙ | |||
3872 3873 3874 3875 3876 3877 3878 | static int clearCell(MemPage *pPage, unsigned char *pCell){ BtShared *pBt = pPage->pBt; CellInfo info; Pgno ovflPgno; int rc; int nOvfl; int ovflPageSize; | < < | | > < | | > | > < | 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 | static int clearCell(MemPage *pPage, unsigned char *pCell){ BtShared *pBt = pPage->pBt; CellInfo info; Pgno ovflPgno; int rc; int nOvfl; int ovflPageSize; parseCellPtr(pPage, pCell, &info); if( info.iOverflow==0 ){ return SQLITE_OK; /* No overflow pages. Return without doing anything */ } ovflPgno = get4byte(&pCell[info.iOverflow]); ovflPageSize = pBt->usableSize - 4; nOvfl = (info.nPayload - info.nLocal + ovflPageSize - 1)/ovflPageSize; assert( ovflPgno==0 || nOvfl>0 ); while( nOvfl-- ){ MemPage *pOvfl; if( ovflPgno==0 || ovflPgno>sqlite3pager_pagecount(pBt->pPager) ){ return SQLITE_CORRUPT_BKPT; } rc = getPage(pBt, ovflPgno, &pOvfl, 0); if( rc ) return rc; if( nOvfl ){ ovflPgno = get4byte(pOvfl->aData); } rc = freePage(pOvfl); sqlite3pager_unref(pOvfl->aData); if( rc ) return rc; } return SQLITE_OK; } /* ** Create the byte sequence used to represent a cell on page pPage ** and write that byte sequence into pCell[]. Overflow pages are ** allocated and filled in as necessary. The calling procedure |
︙ | ︙ | |||
4192 4193 4194 4195 4196 4197 4198 4199 4200 4201 4202 4203 4204 4205 | #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; parseCellPtr(pPage, pCell, &info); if( (info.nData+(pPage->intKey?0:info.nKey))>info.nLocal ){ Pgno pgnoOvfl = get4byte(&pCell[info.iOverflow]); int rc = ptrmapPut(pPage->pBt, pgnoOvfl, PTRMAP_OVERFLOW1, pPage->pgno); if( rc!=SQLITE_OK ) return rc; } } #endif | > | 4194 4195 4196 4197 4198 4199 4200 4201 4202 4203 4204 4205 4206 4207 4208 | #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; parseCellPtr(pPage, pCell, &info); assert( (info.nData+(pPage->intKey?0:info.nKey))==info.nPayload ); if( (info.nData+(pPage->intKey?0:info.nKey))>info.nLocal ){ Pgno pgnoOvfl = get4byte(&pCell[info.iOverflow]); int rc = ptrmapPut(pPage->pBt, pgnoOvfl, PTRMAP_OVERFLOW1, pPage->pgno); if( rc!=SQLITE_OK ) return rc; } } #endif |
︙ | ︙ | |||
6197 6198 6199 6200 6201 6202 6203 6204 6205 6206 6207 6208 6209 6210 | /* Check payload overflow pages */ sprintf(zContext, "On tree page %d cell %d: ", iPage, i); pCell = findCell(pPage,i); parseCellPtr(pPage, pCell, &info); sz = info.nData; if( !pPage->intKey ) sz += info.nKey; if( sz>info.nLocal ){ int nPage = (sz - info.nLocal + usableSize - 5)/(usableSize - 4); Pgno pgnoOvfl = get4byte(&pCell[info.iOverflow]); #ifndef SQLITE_OMIT_AUTOVACUUM if( pBt->autoVacuum ){ checkPtrmap(pCheck, pgnoOvfl, PTRMAP_OVERFLOW1, iPage, zContext); } | > | 6200 6201 6202 6203 6204 6205 6206 6207 6208 6209 6210 6211 6212 6213 6214 | /* Check payload overflow pages */ sprintf(zContext, "On tree page %d cell %d: ", iPage, i); pCell = findCell(pPage,i); parseCellPtr(pPage, pCell, &info); sz = info.nData; if( !pPage->intKey ) sz += info.nKey; assert( sz==info.nPayload ); if( sz>info.nLocal ){ int nPage = (sz - info.nLocal + usableSize - 5)/(usableSize - 4); Pgno pgnoOvfl = get4byte(&pCell[info.iOverflow]); #ifndef SQLITE_OMIT_AUTOVACUUM if( pBt->autoVacuum ){ checkPtrmap(pCheck, pgnoOvfl, PTRMAP_OVERFLOW1, iPage, zContext); } |
︙ | ︙ |