Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Begin trying to get integrity checking working on the new btree.c. (CVS 1329) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
499569daa6a3aed6609bcb1e11a3d231 |
User & Date: | drh 2004-05-09 01:35:06.000 |
Context
2004-05-09
| ||
11:51 | The btree.test test is no working with integrity_check enabled. (CVS 1330) (check-in: 9f1caa530e user: drh tags: trunk) | |
01:35 | Begin trying to get integrity checking working on the new btree.c. (CVS 1329) (check-in: 499569daa6 user: drh tags: trunk) | |
00:40 | All tests in btree.test now pass (but only because I commented out the btree_integrity_check test.) (CVS 1328) (check-in: ee706e9c74 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.118 2004/05/09 01:35:06 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. |
︙ | ︙ | |||
214 215 216 217 218 219 220 | u8 isInit; /* True if previously initialized */ u8 idxShift; /* True if Cell indices have changed */ u8 isOverfull; /* Some aCell[] do not fit on page */ u8 intKey; /* True if intkey flag is set */ u8 leaf; /* True if leaf flag is set */ u8 zeroData; /* True if zero data flag is set */ u8 hdrOffset; /* 100 for page 1. 0 otherwise */ | < | 214 215 216 217 218 219 220 221 222 223 224 225 226 227 | u8 isInit; /* True if previously initialized */ u8 idxShift; /* True if Cell indices have changed */ u8 isOverfull; /* Some aCell[] do not fit on page */ u8 intKey; /* True if intkey flag is set */ u8 leaf; /* True if leaf flag is set */ u8 zeroData; /* True if zero data flag is set */ u8 hdrOffset; /* 100 for page 1. 0 otherwise */ int idxParent; /* Index in pParent->aCell[] of this node */ int nFree; /* Number of free bytes on the page */ int nCell; /* Number of entries on this page */ int nCellAlloc; /* Number of slots allocated in aCell[] */ unsigned char **aCell; /* Pointer to start of each cell */ struct Btree *pBt; /* Pointer back to BTree structure */ |
︙ | ︙ | |||
374 375 376 377 378 379 380 | maxPayload = pPage->pBt->maxLocal; if( nPayload>maxPayload ){ nPayload = maxPayload + 4; } return n + nPayload; } | < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < > | 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 | maxPayload = pPage->pBt->maxLocal; if( nPayload>maxPayload ){ nPayload = maxPayload + 4; } return n + nPayload; } /* ** Defragment the page given. All Cells are moved to the ** beginning of the page and all free space is collected ** into one big FreeBlk at the end of the page. */ static void defragmentPage(MemPage *pPage){ int pc, i, n, addr; int start, hdr, size; int leftover; unsigned char *oldPage; unsigned char newPage[MX_PAGE_SIZE]; assert( sqlite3pager_iswriteable(pPage->aData) ); assert( pPage->pBt!=0 ); assert( pPage->pBt->pageSize <= MX_PAGE_SIZE ); oldPage = pPage->aData; hdr = pPage->hdrOffset; addr = 3+hdr; n = 6+hdr; if( !pPage->leaf ){ n += 4; } memcpy(&newPage[hdr], &oldPage[hdr], n-hdr); start = n; pc = get2byte(&oldPage[addr]); i = 0; while( pc>0 ){ assert( n<pPage->pBt->pageSize ); size = cellSize(pPage, &oldPage[pc]); memcpy(&newPage[n], &oldPage[pc], size); put2byte(&newPage[addr],n); pPage->aCell[i++] = &oldPage[n]; n += size; addr = pc; pc = get2byte(&oldPage[pc]); } assert( i==pPage->nCell ); leftover = pPage->pBt->pageSize - n; assert( leftover>=0 ); assert( pPage->nFree==leftover ); if( leftover<4 ){ |
︙ | ︙ | |||
671 672 673 674 675 676 677 | int pageSize; int sumCell = 0; /* Total size of all cells */ assert( pPage->pBt!=0 ); assert( pParent==0 || pParent->pBt==pPage->pBt ); assert( pPage->pgno==sqlite3pager_pagenumber(pPage->aData) ); assert( pPage->aData == &((unsigned char*)pPage)[-pPage->pBt->pageSize] ); | | > | | > < < | 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 | int pageSize; int sumCell = 0; /* Total size of all cells */ assert( pPage->pBt!=0 ); assert( pParent==0 || pParent->pBt==pPage->pBt ); assert( pPage->pgno==sqlite3pager_pagenumber(pPage->aData) ); assert( pPage->aData == &((unsigned char*)pPage)[-pPage->pBt->pageSize] ); assert( pPage->isInit==0 || pPage->pParent==pParent ); if( pPage->isInit ) return SQLITE_OK; assert( pPage->pParent==0 ); pPage->pParent = pParent; if( pParent ){ sqlite3pager_ref(pParent->aData); } pPage->nCell = pPage->nCellAlloc = 0; assert( pPage->hdrOffset==(pPage->pgno==1 ? 100 : 0) ); hdr = pPage->hdrOffset; data = pPage->aData; c = data[hdr]; pPage->intKey = (c & PTF_INTKEY)!=0; pPage->zeroData = (c & PTF_ZERODATA)!=0; pPage->leaf = (c & PTF_LEAF)!=0; pPage->isOverfull = 0; pPage->idxShift = 0; pageSize = pPage->pBt->pageSize; /* Initialize the cell count and cell pointers */ pc = get2byte(&data[hdr+3]); while( pc>0 ){ if( pc>=pageSize ) return SQLITE_CORRUPT; |
︙ | ︙ | |||
729 730 731 732 733 734 735 | /* Sanity check: Cells and freespace and header must sum to the size ** a page. */ if( sumCell+pPage->nFree+hdr+10-pPage->leaf*4 != pageSize ){ return SQLITE_CORRUPT; } pPage->isInit = 1; | < < < < < < < < | 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 | /* Sanity check: Cells and freespace and header must sum to the size ** a page. */ if( sumCell+pPage->nFree+hdr+10-pPage->leaf*4 != pageSize ){ return SQLITE_CORRUPT; } pPage->isInit = 1; return SQLITE_OK; } /* ** Set up a raw page so that it looks like a database page holding ** no entries. */ static void zeroPage(MemPage *pPage, int flags){ unsigned char *data = pPage->aData; Btree *pBt = pPage->pBt; int hdr = pPage->hdrOffset; int first; assert( sqlite3pager_iswriteable(data) ); memset(&data[hdr], 0, pBt->pageSize - hdr); data[hdr] = flags; first = hdr + 6 + 4*((flags&PTF_LEAF)==0); put2byte(&data[hdr+1], first); put2byte(&data[first+2], pBt->pageSize - first); sqliteFree(pPage->aCell); pPage->aCell = 0; pPage->nCell = 0; pPage->nCellAlloc = 0; pPage->nFree = pBt->pageSize - first; pPage->intKey = (flags & PTF_INTKEY)!=0; pPage->leaf = (flags & PTF_LEAF)!=0; pPage->zeroData = (flags & PTF_ZERODATA)!=0; pPage->hdrOffset = hdr; } /* ** Get a page from the pager. Initialize the MemPage.pBt and ** MemPage.aData elements if needed. */ static int getPage(Btree *pBt, Pgno pgno, MemPage **ppPage){ |
︙ | ︙ | |||
825 826 827 828 829 830 831 | /* ** This routine is called when the reference count for a page ** reaches zero. We need to unref the pParent pointer when that ** happens. */ static void pageDestructor(void *pData){ MemPage *pPage = (MemPage*)&((char*)pData)[SQLITE_PAGE_SIZE]; | < | 741 742 743 744 745 746 747 748 749 750 751 752 753 754 | /* ** This routine is called when the reference count for a page ** reaches zero. We need to unref the pParent pointer when that ** happens. */ static void pageDestructor(void *pData){ MemPage *pPage = (MemPage*)&((char*)pData)[SQLITE_PAGE_SIZE]; if( pPage->pParent ){ MemPage *pParent = pPage->pParent; pPage->pParent = 0; releasePage(pParent); } sqliteFree(pPage->aCell); pPage->aCell = 0; |
︙ | ︙ | |||
1077 1078 1079 1080 1081 1082 1083 | /* ** Invalidate all cursors */ static void invalidateCursors(Btree *pBt){ BtCursor *pCur; for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){ MemPage *pPage = pCur->pPage; | | < < < < < < < < < < < < < < < < < < < | 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 | /* ** Invalidate all cursors */ static void invalidateCursors(Btree *pBt){ BtCursor *pCur; for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){ MemPage *pPage = pCur->pPage; if( pPage && !pPage->isInit ){ releasePage(pPage); pCur->pPage = 0; pCur->isValid = 0; pCur->status = SQLITE_ABORT; } } } /* ** Rollback the transaction in progress. All cursors will be ** invalided by this operation. Any attempt to use a cursor ** that was open at the beginning of this operation will result ** in an error. ** ** This will release the write lock on the database file. If there |
︙ | ︙ | |||
1367 1368 1369 1370 1371 1372 1373 | MemPage *pPage; unsigned char *cell; if( !pCur->isValid ){ *pSize = 0; }else{ pPage = pCur->pPage; | < | 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 | MemPage *pPage; unsigned char *cell; if( !pCur->isValid ){ *pSize = 0; }else{ pPage = pCur->pPage; assert( pPage!=0 ); assert( pCur->idx>=0 && pCur->idx<pPage->nCell ); cell = pPage->aCell[pCur->idx]; cell += 2; /* Skip the offset to the next cell */ if( !pPage->leaf ){ cell += 4; /* Skip the child pointer */ } |
︙ | ︙ | |||
1410 1411 1412 1413 1414 1415 1416 | u64 nData, nKey; int maxLocal, ovflSize; assert( pCur!=0 && pCur->pPage!=0 ); assert( pCur->isValid ); pBt = pCur->pBt; pPage = pCur->pPage; | < | 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 | u64 nData, nKey; int maxLocal, ovflSize; assert( pCur!=0 && pCur->pPage!=0 ); assert( pCur->isValid ); pBt = pCur->pBt; pPage = pCur->pPage; assert( pCur->idx>=0 && pCur->idx<pPage->nCell ); aPayload = pPage->aCell[pCur->idx]; aPayload += 2; /* Skip the next cell index */ if( !pPage->leaf ){ aPayload += 4; /* Skip the child pointer */ } if( pPage->zeroData ){ |
︙ | ︙ | |||
1533 1534 1535 1536 1537 1538 1539 | if( !pCur->isValid ){ return 0; } assert( pCur->pPage!=0 ); assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell ); pBt = pCur->pBt; pPage = pCur->pPage; | < | 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 | if( !pCur->isValid ){ return 0; } assert( pCur->pPage!=0 ); assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell ); pBt = pCur->pBt; pPage = pCur->pPage; assert( pCur->idx>=0 && pCur->idx<pPage->nCell ); assert( pPage->intKey==0 ); aPayload = pPage->aCell[pCur->idx]; aPayload += 2; /* Skip the next cell index */ if( !pPage->leaf ){ aPayload += 4; /* Skip the child pointer */ } |
︙ | ︙ | |||
1570 1571 1572 1573 1574 1575 1576 | if( !pCur->isValid ){ return pCur->status ? pCur->status : SQLITE_INTERNAL; } pPage = pCur->pPage; assert( pPage!=0 ); assert( pPage->isInit ); | < | 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 | if( !pCur->isValid ){ return pCur->status ? pCur->status : SQLITE_INTERNAL; } pPage = pCur->pPage; assert( pPage!=0 ); assert( pPage->isInit ); if( pPage->zeroData ){ *pSize = 0; }else{ assert( pCur->idx>=0 && pCur->idx<pPage->nCell ); cell = pPage->aCell[pCur->idx]; cell += 2; /* Skip the offset to the next cell */ if( !pPage->leaf ){ |
︙ | ︙ | |||
1620 1621 1622 1623 1624 1625 1626 | MemPage *pNewPage; MemPage *pOldPage; Btree *pBt = pCur->pBt; assert( pCur->isValid ); rc = getAndInitPage(pBt, newPgno, &pNewPage, pCur->pPage); if( rc ) return rc; | < | 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 | MemPage *pNewPage; MemPage *pOldPage; Btree *pBt = pCur->pBt; assert( pCur->isValid ); rc = getAndInitPage(pBt, newPgno, &pNewPage, pCur->pPage); if( rc ) return rc; pNewPage->idxParent = pCur->idx; pOldPage = pCur->pPage; pOldPage->idxShift = 0; releasePage(pOldPage); pCur->pPage = pNewPage; pCur->idx = 0; if( pNewPage->nCell<1 ){ |
︙ | ︙ | |||
1644 1645 1646 1647 1648 1649 1650 | ** for the table rooted on page 1, sometime the real root page ** is empty except for the right-pointer. In such cases the ** virtual root page is the page that the right-pointer of page ** 1 is pointing to. */ static int isRootPage(MemPage *pPage){ MemPage *pParent = pPage->pParent; | | | < | 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 | ** for the table rooted on page 1, sometime the real root page ** is empty except for the right-pointer. In such cases the ** virtual root page is the page that the right-pointer of page ** 1 is pointing to. */ static int isRootPage(MemPage *pPage){ MemPage *pParent = pPage->pParent; assert( pParent==0 || pParent->isInit ); if( pParent==0 || (pParent->pgno==1 && pParent->nCell==0) ) return 1; return 0; } /* ** Move the cursor up to the parent page. ** ** pCur->idx is set to the cell index that contains the pointer |
︙ | ︙ | |||
1668 1669 1670 1671 1672 1673 1674 | MemPage *pPage; int idxParent; assert( pCur->isValid ); pPage = pCur->pPage; assert( pPage!=0 ); assert( !isRootPage(pPage) ); | < < | 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 | MemPage *pPage; int idxParent; assert( pCur->isValid ); pPage = pCur->pPage; assert( pPage!=0 ); assert( !isRootPage(pPage) ); pParent = pPage->pParent; assert( pParent!=0 ); idxParent = pPage->idxParent; sqlite3pager_ref(pParent->aData); oldPgno = pPage->pgno; releasePage(pPage); pCur->pPage = pParent; assert( pParent->idxShift==0 ); if( pParent->idxShift==0 ){ |
︙ | ︙ | |||
1721 1722 1723 1724 1725 1726 1727 | rc = getAndInitPage(pBt, pCur->pgnoRoot, &pRoot, 0); if( rc ){ pCur->isValid = 0; return rc; } releasePage(pCur->pPage); | < | 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 | rc = getAndInitPage(pBt, pCur->pgnoRoot, &pRoot, 0); if( rc ){ pCur->isValid = 0; return rc; } releasePage(pCur->pPage); pCur->pPage = pRoot; pCur->idx = 0; if( pRoot->nCell==0 && !pRoot->leaf ){ Pgno subpage; assert( pRoot->pgno==1 ); subpage = get4byte(&pRoot->aData[pRoot->hdrOffset+6]); assert( subpage>0 ); |
︙ | ︙ | |||
1870 1871 1872 1873 1874 1875 1876 | for(;;){ int lwr, upr; Pgno chldPg; MemPage *pPage = pCur->pPage; int c = -1; /* pRes return if table is empty must be -1 */ lwr = 0; upr = pPage->nCell-1; | < | 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 | for(;;){ int lwr, upr; Pgno chldPg; MemPage *pPage = pCur->pPage; int c = -1; /* pRes return if table is empty must be -1 */ lwr = 0; upr = pPage->nCell-1; while( lwr<=upr ){ void *pCellKey; u64 nCellKey; pCur->idx = (lwr+upr)/2; sqlite3BtreeKeySize(pCur, &nCellKey); if( pPage->intKey ){ if( nCellKey<nKey ){ |
︙ | ︙ | |||
2305 2306 2307 2308 2309 2310 2311 | static void reparentPage(Btree *pBt, Pgno pgno, MemPage *pNewParent, int idx){ MemPage *pThis; unsigned char *aData; if( pgno==0 ) return; assert( pBt->pPager!=0 ); aData = sqlite3pager_lookup(pBt->pPager, pgno); | < | | | | | | | | < | 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 | static void reparentPage(Btree *pBt, Pgno pgno, MemPage *pNewParent, int idx){ MemPage *pThis; unsigned char *aData; if( pgno==0 ) return; assert( pBt->pPager!=0 ); aData = sqlite3pager_lookup(pBt->pPager, pgno); pThis = (MemPage*)&aData[pBt->pageSize]; if( pThis && pThis->isInit ){ if( pThis->pParent!=pNewParent ){ if( pThis->pParent ) sqlite3pager_unref(pThis->pParent->aData); pThis->pParent = pNewParent; if( pNewParent ) sqlite3pager_ref(pNewParent->aData); } pThis->idxParent = idx; sqlite3pager_unref(aData); } } /* ** Change the pParent pointer of all children of pPage to point back ** to pPage. |
︙ | ︙ | |||
2350 2351 2352 2353 2354 2355 2356 | ** Remove the i-th cell from pPage. This routine effects pPage only. ** The cell content is not freed or deallocated. It is assumed that ** the cell content has been copied someplace else. This routine just ** removes the reference to the cell from pPage. ** ** "sz" must be the number of bytes in the cell. ** | | < < | > | < < | < < < < < < < < < < < < < < < < < | < < | > | | < | | < < < < < < < < < < < < < < < < < | | 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 2298 2299 2300 2301 2302 2303 2304 2305 2306 2307 2308 2309 2310 2311 2312 2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 | ** Remove the i-th cell from pPage. This routine effects pPage only. ** The cell content is not freed or deallocated. It is assumed that ** the cell content has been copied someplace else. This routine just ** removes the reference to the cell from pPage. ** ** "sz" must be the number of bytes in the cell. ** ** Do not bother maintaining the integrity of the linked list of Cells. ** Only the pPage->aCell[] array is important. The relinkCellList() ** routine will be called soon after this routine in order to rebuild ** the linked list. */ static void dropCell(MemPage *pPage, int idx, int sz){ int j, pc; assert( idx>=0 && idx<pPage->nCell ); assert( sz==cellSize(pPage, pPage->aCell[idx]) ); assert( sqlite3pager_iswriteable(pPage->aData) ); assert( pPage->aCell[idx]>=pPage->aData ); assert( pPage->aCell[idx]<&pPage->aData[pPage->pBt->pageSize-sz] ); pc = Addr(pPage->aCell[idx]) - Addr(pPage->aData); assert( pc>pPage->hdrOffset && pc+sz<=pPage->pBt->pageSize ); freeSpace(pPage, pc, sz); for(j=idx; j<pPage->nCell-1; j++){ pPage->aCell[j] = pPage->aCell[j+1]; } pPage->nCell--; pPage->idxShift = 1; } /* ** 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 ** will not fit, then just make pPage->aCell[i] point to the content ** and set pPage->isOverfull. ** ** Do not bother maintaining the integrity of the linked list of Cells. ** Only the pPage->aCell[] array is important. The relinkCellList() ** routine will be called soon after this routine in order to rebuild ** the linked list. */ static void insertCell(MemPage *pPage, int i, unsigned char *pCell, int sz){ int idx, j; assert( i>=0 && i<=pPage->nCell ); assert( sz==cellSize(pPage, pCell) ); assert( sqlite3pager_iswriteable(pPage->aData) ); idx = allocateSpace(pPage, sz); resizeCellArray(pPage, pPage->nCell+1); for(j=pPage->nCell; j>i; j--){ pPage->aCell[j] = pPage->aCell[j-1]; } pPage->nCell++; if( idx<=0 ){ pPage->isOverfull = 1; pPage->aCell[i] = pCell; }else{ memcpy(&pPage->aData[idx], pCell, sz); pPage->aCell[i] = &pPage->aData[idx]; } pPage->idxShift = 1; } /* ** Rebuild the linked list of cells on a page so that the cells ** occur in the order specified by the pPage->aCell[] array. ** Invoke this routine once to repair damage after one or more ** invocations of either insertCell() or dropCell(). */ static void relinkCellList(MemPage *pPage){ int i, idxFrom; assert( sqlite3pager_iswriteable(pPage->aData) ); idxFrom = pPage->hdrOffset+3; for(i=0; i<pPage->nCell; i++){ int idx = Addr(pPage->aCell[i]) - Addr(pPage->aData); assert( idx>pPage->hdrOffset && idx<pPage->pBt->pageSize ); put2byte(&pPage->aData[idxFrom], idx); idxFrom = idx; } put2byte(&pPage->aData[idxFrom], 0); } /* ** GCC does not define the offsetof() macro so we'll have to do it ** ourselves. */ #ifndef offsetof #define offsetof(STRUCTURE,FIELD) ((int)((char*)&((STRUCTURE*)0)->FIELD)) #endif /* ** Move the content of the page at pFrom over to pTo. The pFrom->aCell[] ** pointers that point into pFrom->aData[] must be adjusted to point ** into pTo->aData[] instead. But some pFrom->aCell[] entries might ** not point to pFrom->aData[]. Those are unchanged. ** ** Over this operation completes, the meta data for pFrom is zeroed. */ static void copyPage(MemPage *pTo, MemPage *pFrom){ uptr from, to; int i; int pageSize; int ofst; assert( pTo->hdrOffset==0 ); ofst = pFrom->hdrOffset; |
︙ | ︙ | |||
2507 2508 2509 2510 2511 2512 2513 | uptr x = Addr(pTo->aCell[i]); if( x>from && x<from+pageSize-ofst ){ *((uptr*)&pTo->aCell[i]) = x + to - from; } } } | < < < < < < < < < | 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 | uptr x = Addr(pTo->aCell[i]); if( x>from && x<from+pageSize-ofst ){ *((uptr*)&pTo->aCell[i]) = x + to - from; } } } /* ** The following parameters determine how many adjacent pages get involved ** in a balancing operation. NN is the number of neighbors on either side ** of the page that participate in the balancing operation. NB is the ** total number of pages that participate, including the target page and ** NN neighbors on either side. ** |
︙ | ︙ | |||
2581 2582 2583 2584 2585 2586 2587 | int idx; /* Index of pPage in pParent->aCell[] */ int nxDiv; /* Next divider slot in pParent->aCell[] */ int rc; /* The return code */ int leafCorrection; /* 4 if pPage is a leaf. 0 if not */ int usableSpace; /* Bytes in pPage beyond the header */ int pageFlags; /* Value of pPage->aData[0] */ int subtotal; /* Subtotal of bytes in cells on one page */ | < | 2417 2418 2419 2420 2421 2422 2423 2424 2425 2426 2427 2428 2429 2430 | int idx; /* Index of pPage in pParent->aCell[] */ int nxDiv; /* Next divider slot in pParent->aCell[] */ int rc; /* The return code */ int leafCorrection; /* 4 if pPage is a leaf. 0 if not */ int usableSpace; /* Bytes in pPage beyond the header */ int pageFlags; /* Value of pPage->aData[0] */ int subtotal; /* Subtotal of bytes in cells on one page */ MemPage *apOld[NB]; /* pPage and up to two siblings */ Pgno pgnoOld[NB]; /* Page numbers for each page in apOld[] */ MemPage *apCopy[NB]; /* Private copies of apOld[] pages */ MemPage *apNew[NB+1]; /* pPage and up to NB siblings after balancing */ Pgno pgnoNew[NB+1]; /* Page numbers for each page in apNew[] */ int idxDiv[NB]; /* Indices of divider cells in pParent */ u8 *apDiv[NB]; /* Divider cells in pParent */ |
︙ | ︙ | |||
2612 2613 2614 2615 2616 2617 2618 | } /* ** Find the parent of the page to be balanced. If there is no parent, ** it means this page is the root page and special rules apply. */ pParent = pPage->pParent; | < < | 2447 2448 2449 2450 2451 2452 2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 | } /* ** Find the parent of the page to be balanced. If there is no parent, ** it means this page is the root page and special rules apply. */ pParent = pPage->pParent; if( pParent==0 ){ Pgno pgnoChild; MemPage *pChild; assert( pPage->isInit ); if( pPage->nCell==0 ){ if( pPage->leaf ){ /* The table is completely empty */ relinkCellList(pPage); }else{ /* The root page is empty but has one child. Transfer the ** information from that one child into the root page if it ** will fit. This reduces the depth of the BTree by one. ** ** If the root page is page 1, it has less space available than ** its child (due to the 100 byte header that occurs at the beginning |
︙ | ︙ | |||
2652 2653 2654 2655 2656 2657 2658 | zeroPage(pPage, pChild->aData[0]); resizeCellArray(pPage, pChild->nCell); for(i=0; i<pChild->nCell; i++){ insertCell(pPage, i, pChild->aCell[i], cellSize(pChild, pChild->aCell[i])); } freePage(pChild); | < < < < | < > | < | 2485 2486 2487 2488 2489 2490 2491 2492 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514 2515 2516 2517 2518 2519 2520 2521 2522 2523 2524 2525 2526 2527 2528 2529 2530 2531 2532 2533 2534 2535 2536 2537 2538 2539 2540 2541 2542 2543 | zeroPage(pPage, pChild->aData[0]); resizeCellArray(pPage, pChild->nCell); for(i=0; i<pChild->nCell; i++){ insertCell(pPage, i, pChild->aCell[i], cellSize(pChild, pChild->aCell[i])); } freePage(pChild); }else{ /* The child has more information that will fit on the root. ** The tree is already balanced. Do nothing. */ } }else{ memcpy(pPage, pChild, pBt->pageSize); pPage->isInit = 0; pPage->pParent = 0; rc = initPage(pPage, 0); assert( rc==SQLITE_OK ); freePage(pChild); } reparentChildPages(pPage); releasePage(pChild); } return SQLITE_OK; } if( !pPage->isOverfull ){ /* It is OK for the root page to be less than half full. */ relinkCellList(pPage); return SQLITE_OK; } /* ** If we get to here, it means the root page is overfull. ** When this happens, Create a new child page and copy the ** contents of the root into the child. Then make the root ** page an empty page with rightChild pointing to the new ** child. Then fall thru to the code below which will cause ** the overfull child page to be split. */ rc = allocatePage(pBt, &pChild, &pgnoChild, pPage->pgno); if( rc ) return rc; assert( sqlite3pager_iswriteable(pChild->aData) ); copyPage(pChild, pPage); assert( pChild->aData[0]==pPage->aData[pPage->hdrOffset] ); pChild->pParent = pPage; pChild->idxParent = 0; sqlite3pager_ref(pPage->aData); pChild->isOverfull = 1; zeroPage(pPage, pChild->aData[0] & ~PTF_LEAF); put4byte(&pPage->aData[pPage->hdrOffset+6], pChild->pgno); pParent = pPage; pPage = pChild; initPage(pParent, 0); } rc = sqlite3pager_write(pParent->aData); if( rc ) return rc; assert( pParent->isInit ); /* ** Find the cell in the parent page whose left child points back |
︙ | ︙ | |||
2778 2779 2780 2781 2782 2783 2784 | ** The rest of this function will use data from the copies rather ** that the original pages since the original pages will be in the ** process of being overwritten. */ for(i=0; i<nOld; i++){ MemPage *p = apCopy[i] = (MemPage*)&aCopy[i+1][-sizeof(MemPage)]; p->aData = &((u8*)p)[-pBt->pageSize]; | < < | | 2606 2607 2608 2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619 2620 | ** The rest of this function will use data from the copies rather ** that the original pages since the original pages will be in the ** process of being overwritten. */ for(i=0; i<nOld; i++){ MemPage *p = apCopy[i] = (MemPage*)&aCopy[i+1][-sizeof(MemPage)]; p->aData = &((u8*)p)[-pBt->pageSize]; copyPage(p, apOld[i]); } /* ** Load pointers to all cells on sibling pages and the divider cells ** into the local apCell[] array. Make copies of the divider cells ** into aTemp[] and remove the the divider Cells from pParent. ** |
︙ | ︙ | |||
2805 2806 2807 2808 2809 2810 2811 | MemPage *pOld = apCopy[i]; for(j=0; j<pOld->nCell; j++){ apCell[nCell] = pOld->aCell[j]; szCell[nCell] = cellSize(pOld, apCell[nCell]); nCell++; } if( i<nOld-1 ){ | | | < | | 2631 2632 2633 2634 2635 2636 2637 2638 2639 2640 2641 2642 2643 2644 2645 2646 2647 2648 2649 | MemPage *pOld = apCopy[i]; for(j=0; j<pOld->nCell; j++){ apCell[nCell] = pOld->aCell[j]; szCell[nCell] = cellSize(pOld, apCell[nCell]); nCell++; } if( i<nOld-1 ){ szCell[nCell] = cellSize(pParent, apDiv[i]) - leafCorrection; memcpy(aTemp[i], apDiv[i], szCell[nCell] + leafCorrection); apCell[nCell] = &aTemp[i][leafCorrection]; dropCell(pParent, nxDiv, szCell[nCell]); assert( get4byte(&apCell[nCell][2])==pgnoOld[i] ); if( !pOld->leaf ){ assert( leafCorrection==0 ); /* The right pointer of the child page pOld becomes the left ** pointer of the divider cell */ memcpy(&apCell[nCell][2], &pOld->aData[pOld->hdrOffset+6], 4); }else{ assert( leafCorrection==4 ); |
︙ | ︙ | |||
2862 2863 2864 2865 2866 2867 2868 | /* ** Allocate k new pages. Reuse old pages where possible. */ assert( pPage->pgno>1 ); pageFlags = pPage->aData[0]; for(i=0; i<k; i++){ | < | | | < | > | | 2687 2688 2689 2690 2691 2692 2693 2694 2695 2696 2697 2698 2699 2700 2701 2702 2703 2704 2705 2706 2707 2708 2709 2710 2711 2712 2713 2714 2715 2716 2717 2718 2719 2720 | /* ** Allocate k new pages. Reuse old pages where possible. */ assert( pPage->pgno>1 ); pageFlags = pPage->aData[0]; for(i=0; i<k; i++){ if( i<nOld ){ apNew[i] = apOld[i]; pgnoNew[i] = pgnoOld[i]; apOld[i] = 0; sqlite3pager_write(apNew[i]->aData); }else{ rc = allocatePage(pBt, &apNew[i], &pgnoNew[i], pgnoNew[i-1]); if( rc ) goto balance_cleanup; } nNew++; zeroPage(apNew[i], pageFlags); apNew[i]->isInit = 1; } /* Free any old pages that were not reused as new pages. */ while( i<nOld ){ rc = freePage(apOld[i]); if( rc ) goto balance_cleanup; sqlite3pager_unref(apOld[i]->aData); apOld[i] = 0; i++; } /* ** Put the new pages in accending order. This helps to ** keep entries in the disk file in order so that a scan |
︙ | ︙ | |||
2976 2977 2978 2979 2980 2981 2982 | reparentChildPages(apNew[i]); } reparentChildPages(pParent); /* ** balance the parent page. */ | < < < < > < < | 2800 2801 2802 2803 2804 2805 2806 2807 2808 2809 2810 2811 2812 2813 2814 2815 2816 2817 2818 2819 2820 2821 2822 2823 2824 2825 2826 2827 2828 2829 2830 | reparentChildPages(apNew[i]); } reparentChildPages(pParent); /* ** balance the parent page. */ rc = balance(pParent); /* ** Cleanup before returning. */ balance_cleanup: for(i=0; i<nOld; i++){ releasePage(apOld[i]); if( apCopy[i] ){ releasePage(apCopy[i]->pParent); sqliteFree(apCopy[i]->aCell); } } for(i=0; i<nNew; i++){ releasePage(apNew[i]); } releasePage(pParent); return rc; } /* ** This routine checks all cursors that point to the same table ** as pCur points to. If any of those cursors were opened with ** wrFlag==0 then this routine returns SQLITE_LOCKED. If all |
︙ | ︙ | |||
3149 3150 3151 3152 3153 3154 3155 | ** next Cell after the one to be deleted is guaranteed to exist and ** to be a leaf so we can use it. */ BtCursor leafCur; unsigned char *pNext; int szNext; int notUsed; | < | < < | 2968 2969 2970 2971 2972 2973 2974 2975 2976 2977 2978 2979 2980 2981 2982 2983 2984 2985 2986 2987 2988 2989 2990 2991 2992 2993 2994 2995 2996 | ** next Cell after the one to be deleted is guaranteed to exist and ** to be a leaf so we can use it. */ BtCursor leafCur; unsigned char *pNext; int szNext; int notUsed; getTempCursor(pCur, &leafCur); rc = sqlite3BtreeNext(&leafCur, ¬Used); if( rc!=SQLITE_OK ){ if( rc!=SQLITE_NOMEM ) rc = SQLITE_CORRUPT; return rc; } rc = sqlite3pager_write(leafCur.pPage->aData); if( rc ) return rc; dropCell(pPage, pCur->idx, cellSize(pPage, pCell)); pNext = leafCur.pPage->aCell[leafCur.idx]; szNext = cellSize(leafCur.pPage, pNext); insertCell(pPage, pCur->idx, &pNext[-4], szNext+4); put4byte(&pNext[-2], pgnoChild); rc = balance(pPage); if( rc ) return rc; dropCell(leafCur.pPage, leafCur.idx, szNext); rc = balance(leafCur.pPage); releaseTempCursor(&leafCur); }else{ dropCell(pPage, pCur->idx, cellSize(pPage, pCell)); rc = balance(pPage); } |
︙ | ︙ | |||
3370 3371 3372 3373 3374 3375 3376 | } hdr = pPage->hdrOffset; data = pPage->aData; c = data[hdr]; pPage->intKey = (c & PTF_INTKEY)!=0; pPage->zeroData = (c & PTF_ZERODATA)!=0; pPage->leaf = (c & PTF_LEAF)!=0; | | | < | 3186 3187 3188 3189 3190 3191 3192 3193 3194 3195 3196 3197 3198 3199 3200 3201 | } hdr = pPage->hdrOffset; data = pPage->aData; c = data[hdr]; pPage->intKey = (c & PTF_INTKEY)!=0; pPage->zeroData = (c & PTF_ZERODATA)!=0; pPage->leaf = (c & PTF_LEAF)!=0; printf("PAGE %d: flags=0x%02x frag=%d\n", pgno, data[hdr], data[hdr+5]); i = 0; assert( hdr == (pgno==1 ? 100 : 0) ); idx = get2byte(&data[hdr+3]); while( idx>0 && idx<=pBt->pageSize ){ u64 nData, nKey; int nHeader; Pgno child; |
︙ | ︙ | |||
3468 3469 3470 3471 3472 3473 3474 | ** aResult[4] = Number of free bytes on this page ** aResult[5] = Number of free blocks on the page ** aResult[6] = Page number of the left child of this entry ** aResult[7] = Page number of the right child for the whole page ** ** This routine is used for testing and debugging only. */ | | < < | 3283 3284 3285 3286 3287 3288 3289 3290 3291 3292 3293 3294 3295 3296 3297 3298 3299 | ** aResult[4] = Number of free bytes on this page ** aResult[5] = Number of free blocks on the page ** aResult[6] = Page number of the left child of this entry ** aResult[7] = Page number of the right child for the whole page ** ** This routine is used for testing and debugging only. */ int sqlite3BtreeCursorDump(BtCursor *pCur, int *aResult){ int cnt, idx; MemPage *pPage = pCur->pPage; assert( pPage->isInit ); aResult[0] = sqlite3pager_pagenumber(pPage->aData); assert( aResult[0]==pPage->pgno ); aResult[1] = pCur->idx; aResult[2] = pPage->nCell; if( pCur->idx>=0 && pCur->idx<pPage->nCell ){ aResult[3] = cellSize(pPage, pPage->aCell[pCur->idx]); |
︙ | ︙ |
Changes to test/btree.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 script is btree database backend # | | | 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 script is btree database backend # # $Id: btree.test,v 1.22 2004/05/09 01:35:06 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl # Basic functionality. Open and close a database. # |
︙ | ︙ | |||
612 613 614 615 616 617 618 | #btree_page_dump $::b1 2 do_test btree-7.15 { lindex [btree_pager_stats $::b1] 1 } {1} # Check to see that data on overflow pages work correctly. # | < | 612 613 614 615 616 617 618 619 620 621 622 623 624 625 | #btree_page_dump $::b1 2 do_test btree-7.15 { lindex [btree_pager_stats $::b1] 1 } {1} # Check to see that data on overflow pages work correctly. # do_test btree-8.1 { set data "*** This is a very long key " while {[string length $data]<1234} {append data $data} set ::data $data btree_insert $::c1 2020 $data } {} #btree_page_dump $::b1 1 |
︙ | ︙ | |||
637 638 639 640 641 642 643 644 645 646 647 648 649 650 | } $::data do_test btree-8.4 { btree_delete $::c1 } {} do_test btree-8.4.1 { lindex [btree_get_meta $::b1] 0 } [expr {int(([string length $::data]-238+1019)/1020)}] do_test btree-8.5 { set data "*** This is an even longer key " while {[string length $data]<2000} {append data $data} append data END set ::data $data btree_insert $::c1 2030 $data } {} | > > > | 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 | } $::data do_test btree-8.4 { btree_delete $::c1 } {} do_test btree-8.4.1 { lindex [btree_get_meta $::b1] 0 } [expr {int(([string length $::data]-238+1019)/1020)}] do_test btree-8.4.2 { btree_integrity_check $::b1 1 2 } {} do_test btree-8.5 { set data "*** This is an even longer key " while {[string length $data]<2000} {append data $data} append data END set ::data $data btree_insert $::c1 2030 $data } {} |
︙ | ︙ | |||
727 728 729 730 731 732 733 | #btree_page_dump $::b1 2 do_test btree-8.21 { lindex [btree_get_meta $::b1] 0 } {2} do_test btree-8.22 { lindex [btree_pager_stats $::b1] 1 } {2} | | > > > > > > | > > > | 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 | #btree_page_dump $::b1 2 do_test btree-8.21 { lindex [btree_get_meta $::b1] 0 } {2} do_test btree-8.22 { lindex [btree_pager_stats $::b1] 1 } {2} do_test btree-8.23.1 { btree_close_cursor $::c1 btree_drop_table $::b1 2 btree_integrity_check $::b1 1 } {} do_test btree-8.23.2 { btree_create_table $::b1 0 } {2} do_test btree_8.23.3 { set ::c1 [btree_cursor $::b1 2 1] lindex [btree_get_meta $::b1] 0 } {4} do_test btree-8.24 { lindex [btree_pager_stats $::b1] 1 } {2} #btree_pager_ref_dump $::b1 do_test btree-8.25 { btree_integrity_check $::b1 1 2 } {} # Check page splitting logic # do_test btree-9.1 { for {set i 1} {$i<=19} {incr i} { set key [format %03d $i] set data "*** $key *** $key *** $key *** $key ***" |
︙ | ︙ | |||
803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 | }] "*** [format %03d $i] ***" } #btree_pager_ref_dump $::b1 do_test btree-9.6 { btree_close_cursor $::c1 lindex [btree_pager_stats $::b1] 1 } {1} do_test btree-9.7 { btree_rollback $::b1 lindex [btree_pager_stats $::b1] 1 } {0} # Create a tree of depth two. That is, there is a single divider entry # on the root pages and two leaf pages. Then delete the divider entry # see what happens. # do_test btree-10.1 { btree_begin_transaction $::b1 | > > > > > | 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 | }] "*** [format %03d $i] ***" } #btree_pager_ref_dump $::b1 do_test btree-9.6 { btree_close_cursor $::c1 lindex [btree_pager_stats $::b1] 1 } {1} puts "222: [btree_integrity_check $::b1 1 2]" do_test btree-9.7 { btree_rollback $::b1 lindex [btree_pager_stats $::b1] 1 } {0} do_test btree-9.8 { btree_integrity_check $::b1 1 2 } {} # Create a tree of depth two. That is, there is a single divider entry # on the root pages and two leaf pages. Then delete the divider entry # see what happens. # do_test btree-10.1 { btree_begin_transaction $::b1 |
︙ | ︙ | |||
959 960 961 962 963 964 965 | btree_next $::c1 btree_data $::c1 } $::data do_test btree-12.12 { btree_next $::c1 btree_key $::c1 } {402} | > > | | | | 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 | btree_next $::c1 btree_data $::c1 } $::data do_test btree-12.12 { btree_next $::c1 btree_key $::c1 } {402} btree_commit $::b1 btree_tree_dump $::b1 1 do_test btree-13.1 { btree_integrity_check $::b1 1 2 } {} # To Do: # # 1. Do some deletes from the 3-layer tree # 2. Commit and reopen the database # 3. Read every 15th entry and make sure it works # 4. Implement btree_sanity and put it throughout this script |
︙ | ︙ |