Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | All tests in btree.test now pass (but only because I commented out the btree_integrity_check test.) (CVS 1328) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
ee706e9c74c3fb32fc3369db226fad9e |
User & Date: | drh 2004-05-09 00:40:52.000 |
Context
2004-05-09
| ||
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) | |
2004-05-08
| ||
20:07 | More btree.c bug fixes. (CVS 1327) (check-in: e9f84ff3fe 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.117 2004/05/09 00:40:52 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 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 */ | > | 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 | 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 */ u8 needRelink; /* True if need to run relinkCellList() */ 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 */ |
︙ | ︙ | |||
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 | 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; | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > < | 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 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 | maxPayload = pPage->pBt->maxLocal; if( nPayload>maxPayload ){ nPayload = maxPayload + 4; } return n + nPayload; } /* ** Do sanity checking on a page. Throw an exception if anything is ** not right. ** ** This routine is used for internal error checking only. It is omitted ** from most builds. */ #if defined(BTREE_DEBUG) && !defined(NDEBUG) && 0 static void _pageIntegrity(MemPage *pPage){ int pageSize; u8 *data; int i, idx, c, pc, hdr, nFree; u8 used[MX_PAGE_SIZE]; pageSize = pPage->pBt->pageSize; assert( pPage->aData==&((unsigned char*)pPage)[-pageSize] ); hdr = pPage->hdrOffset; assert( hdr==(pPage->pgno==1 ? 100 : 0) ); assert( pPage->pgno==sqlite3pager_pagenumber(pPage->aData) ); c = pPage->aData[hdr]; if( pPage->isInit ){ assert( pPage->leaf == ((c & PTF_LEAF)!=0) ); assert( pPage->zeroData == ((c & PTF_ZERODATA)!=0) ); assert( pPage->intKey == ((c & PTF_INTKEY)!=0) ); } data = pPage->aData; memset(used, 0, pageSize); for(i=0; i<hdr+10-pPage->leaf*4; i++) used[i] = 1; nFree = 0; pc = get2byte(&data[hdr+1]); while( pc ){ int size; assert( pc>0 && pc<pageSize-4 ); size = get2byte(&data[pc+2]); assert( pc+size<=pageSize ); nFree += size; for(i=pc; i<pc+size; i++){ assert( used[i]==0 ); used[i] = 1; } pc = get2byte(&data[pc]); } assert( pPage->isInit==0 || pPage->nFree==nFree+data[hdr+5] ); idx = 0; pc = get2byte(&data[hdr+3]); while( pc ){ int size; assert( pPage->isInit==0 || idx<pPage->nCell ); assert( pc>0 && pc<pageSize-4 ); assert( pPage->isInit==0 || pPage->aCell[idx]==&data[pc] ); size = cellSize(pPage, &data[pc]); assert( pc+size<=pageSize ); for(i=pc; i<pc+size; i++){ assert( used[i]==0 ); used[i] = 1; } pc = get2byte(&data[pc]); idx++; } assert( idx==pPage->nCell ); nFree = 0; for(i=0; i<pageSize; i++){ assert( used[i]<=1 ); if( used[i]==0 ) nFree++; } assert( nFree==data[hdr+5] ); } #define pageIntegrity(X) _pageIntegrity(X) #else # define pageIntegrity(X) #endif /* ** 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 ); assert( !pPage->needRelink ); assert( !pPage->isOverfull ); 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); assert( pPage->aCell[i]==&oldPage[pc] ); pPage->aCell[i++] = &oldPage[n]; addr = n; n += size; pc = get2byte(&oldPage[pc]); } assert( i==pPage->nCell ); leftover = pPage->pBt->pageSize - n; assert( leftover>=0 ); assert( pPage->nFree==leftover ); if( leftover<4 ){ |
︙ | ︙ | |||
610 611 612 613 614 615 616 617 618 619 620 621 622 623 | 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; | > | 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 | 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->needRelink = 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; |
︙ | ︙ | |||
652 653 654 655 656 657 658 659 660 661 662 663 664 665 | /* 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. */ | > | 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 | /* 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; pageIntegrity(pPage); return SQLITE_OK; } /* ** Set up a raw page so that it looks like a database page holding ** no entries. */ |
︙ | ︙ | |||
683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 | 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; pPage->isOverfull = 0; pPage->idxShift = 0; pPage->isInit = 1; } /* ** 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){ | > > | 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 | 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; pPage->isOverfull = 0; pPage->needRelink = 0; pPage->idxShift = 0; pPage->isInit = 1; pageIntegrity(pPage); } /* ** 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){ |
︙ | ︙ | |||
745 746 747 748 749 750 751 752 753 754 755 756 757 758 | /* ** 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; | > | 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 | /* ** 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]; assert( pPage->isInit==0 || pPage->needRelink==0 ); if( pPage->pParent ){ MemPage *pParent = pPage->pParent; pPage->pParent = 0; releasePage(pParent); } sqliteFree(pPage->aCell); pPage->aCell = 0; |
︙ | ︙ | |||
996 997 998 999 1000 1001 1002 | /* ** Invalidate all cursors */ static void invalidateCursors(Btree *pBt){ BtCursor *pCur; for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){ MemPage *pPage = pCur->pPage; | | > | 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 | /* ** 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 */ ){ pageIntegrity(pPage); releasePage(pPage); pCur->pPage = 0; pCur->isValid = 0; pCur->status = SQLITE_ABORT; } } } |
︙ | ︙ | |||
1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 | 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 */ } | > | 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 | MemPage *pPage; unsigned char *cell; if( !pCur->isValid ){ *pSize = 0; }else{ pPage = pCur->pPage; pageIntegrity(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 */ } |
︙ | ︙ | |||
1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 | 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 ){ | > | 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 | u64 nData, nKey; int maxLocal, ovflSize; assert( pCur!=0 && pCur->pPage!=0 ); assert( pCur->isValid ); pBt = pCur->pBt; pPage = pCur->pPage; pageIntegrity(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 ){ |
︙ | ︙ | |||
1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 | 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 */ } | > | 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 | if( !pCur->isValid ){ return 0; } assert( pCur->pPage!=0 ); assert( pCur->idx>=0 && pCur->idx<pCur->pPage->nCell ); pBt = pCur->pBt; pPage = pCur->pPage; pageIntegrity(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 */ } |
︙ | ︙ | |||
1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 | 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 ){ | > | 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 | if( !pCur->isValid ){ return pCur->status ? pCur->status : SQLITE_INTERNAL; } pPage = pCur->pPage; assert( pPage!=0 ); assert( pPage->isInit ); pageIntegrity(pPage); 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 ){ |
︙ | ︙ | |||
1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 | 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 ){ | > | 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 | MemPage *pNewPage; MemPage *pOldPage; Btree *pBt = pCur->pBt; assert( pCur->isValid ); rc = getAndInitPage(pBt, newPgno, &pNewPage, pCur->pPage); if( rc ) return rc; pageIntegrity(pNewPage); pNewPage->idxParent = pCur->idx; pOldPage = pCur->pPage; pOldPage->idxShift = 0; releasePage(pOldPage); pCur->pPage = pNewPage; pCur->idx = 0; if( pNewPage->nCell<1 ){ |
︙ | ︙ | |||
1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 | 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 ){ | > > | 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 | MemPage *pPage; int idxParent; assert( pCur->isValid ); pPage = pCur->pPage; assert( pPage!=0 ); assert( !isRootPage(pPage) ); pageIntegrity(pPage); pParent = pPage->pParent; assert( pParent!=0 ); pageIntegrity(pParent); idxParent = pPage->idxParent; sqlite3pager_ref(pParent->aData); oldPgno = pPage->pgno; releasePage(pPage); pCur->pPage = pParent; assert( pParent->idxShift==0 ); if( pParent->idxShift==0 ){ |
︙ | ︙ | |||
1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 | 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 ); | > | 1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 | rc = getAndInitPage(pBt, pCur->pgnoRoot, &pRoot, 0); if( rc ){ pCur->isValid = 0; return rc; } releasePage(pCur->pPage); pageIntegrity(pRoot); 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 ); |
︙ | ︙ | |||
1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 | 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 ){ | > | 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 | 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; pageIntegrity(pPage); while( lwr<=upr ){ void *pCellKey; u64 nCellKey; pCur->idx = (lwr+upr)/2; sqlite3BtreeKeySize(pCur, &nCellKey); if( pPage->intKey ){ if( nCellKey<nKey ){ |
︙ | ︙ | |||
2214 2215 2216 2217 2218 2219 2220 | 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); | > | | | | | | | | > | 2305 2306 2307 2308 2309 2310 2311 2312 2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 | 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); if( aData ){ pThis = (MemPage*)&aData[pBt->pageSize]; if( 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. |
︙ | ︙ | |||
2257 2258 2259 2260 2261 2262 2263 | ** 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. ** | | > > | < | > > | > > > > > > > > > > > > > > > > > | > > | < | | > | | > > > > > > > > > > > > > > > > > | 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391 2392 2393 2394 2395 2396 2397 2398 2399 2400 2401 2402 2403 2404 2405 2406 2407 2408 2409 2410 2411 2412 2413 2414 2415 2416 2417 2418 2419 2420 2421 2422 2423 2424 2425 2426 2427 2428 2429 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447 2448 2449 2450 2451 2452 2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 2469 2470 2471 2472 2473 2474 2475 | ** 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. ** ** Try to maintain the integrity of the linked list of cells. But if ** the cell being inserted does not fit on the page, this will not be ** possible. If the linked list is not maintained, then just update ** pPage->aCell[] and set the pPage->needRelink flag so that we will ** know to rebuild the linked list later. */ static void dropCell(MemPage *pPage, int idx, int sz){ int j, pc; u8 *data; 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] ); data = pPage->aData; pc = Addr(pPage->aCell[idx]) - Addr(data); 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--; if( !pPage->isOverfull && !pPage->needRelink ){ u8 *pPrev; if( idx==0 ){ pPrev = &data[pPage->hdrOffset+3]; }else{ pPrev = pPage->aCell[idx-1]; } if( idx<pPage->nCell ){ pc = Addr(pPage->aCell[idx]) - Addr(data); }else{ pc = 0; } put2byte(pPrev, pc); pageIntegrity(pPage); }else{ pPage->needRelink = 1; } 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. ** ** Try to maintain the integrity of the linked list of cells. But if ** the cell being inserted does not fit on the page, this will not be ** possible. If the linked list is not maintained, then just update ** pPage->aCell[] and set the pPage->needRelink flag so that we will ** know to rebuild the linked list later. */ 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 = pPage->needRelink ? 0 : 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{ u8 *data = pPage->aData; memcpy(&data[idx], pCell, sz); pPage->aCell[i] = &data[idx]; } if( !pPage->isOverfull && !pPage->needRelink ){ u8 *pPrev; int pc; if( i==0 ){ pPrev = &pPage->aData[pPage->hdrOffset+3]; }else{ pPrev = pPage->aCell[i-1]; } pc = get2byte(pPrev); put2byte(pPrev, idx); put2byte(pPage->aCell[i], pc); pageIntegrity(pPage); }else{ pPage->needRelink = 1; } 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) ); if( !pPage->needRelink ) return; 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); pPage->needRelink = 0; } /* ** GCC does not define the offsetof() macro so we'll have to do it ** ourselves. */ #ifndef offsetof |
︙ | ︙ | |||
2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 | 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. ** | > > > > > > > > > | 2507 2508 2509 2510 2511 2512 2513 2514 2515 2516 2517 2518 2519 2520 2521 2522 2523 2524 2525 2526 2527 2528 2529 | uptr x = Addr(pTo->aCell[i]); if( x>from && x<from+pageSize-ofst ){ *((uptr*)&pTo->aCell[i]) = x + to - from; } } } /* ** For debugging... */ #if 1 # define TRACE(X) if( pager3_refinfo_enable ) printf X #else # define TRACE(X) #endif /* ** 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. ** |
︙ | ︙ | |||
2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 2492 | } /* ** 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 | > > | 2612 2613 2614 2615 2616 2617 2618 2619 2620 2621 2622 2623 2624 2625 2626 2627 2628 2629 2630 2631 2632 2633 2634 2635 | } /* ** 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; TRACE(("BALANCE: begin page %d\n", pPage->pgno)); if( pParent==0 ){ Pgno pgnoChild; MemPage *pChild; assert( pPage->isInit ); if( pPage->nCell==0 ){ if( pPage->leaf ){ /* The table is completely empty */ relinkCellList(pPage); TRACE(("BALANCE: empty table\n")); }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 |
︙ | ︙ | |||
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 | > > > > | 2652 2653 2654 2655 2656 2657 2658 2659 2660 2661 2662 2663 2664 2665 2666 2667 2668 2669 2670 2671 2672 2673 2674 2675 2676 2677 2678 2679 2680 2681 2682 2683 2684 2685 2686 2687 2688 2689 2690 | 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); TRACE(("BALANCE: child %d transfer to page 1\n", pChild->pgno)); }else{ /* The child has more information that will fit on the root. ** The tree is already balanced. Do nothing. */ TRACE(("BALANCE: child %d will not fit on page 1\n", pChild->pgno)); } }else{ memcpy(pPage, pChild, pBt->pageSize); pPage->isInit = 0; pPage->pParent = 0; rc = initPage(pPage, 0); assert( rc==SQLITE_OK ); freePage(pChild); TRACE(("BALANCE: transfer child %d into root\n", pChild->pgno)); } 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); TRACE(("BALANCE: Root page is underfull but that is ok\n")); 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 |
︙ | ︙ | |||
2554 2555 2556 2557 2558 2559 2560 2561 2562 2563 2564 2565 2566 2567 | pChild->idxParent = 0; pChild->isOverfull = 1; zeroPage(pPage, pChild->aData[0] & ~PTF_LEAF); put4byte(&pPage->aData[pPage->hdrOffset+6], pChild->pgno); pParent = pPage; pPage = pChild; extraUnref = pChild; } rc = sqlite3pager_write(pParent->aData); if( rc ) return rc; assert( pParent->isInit ); /* ** Find the cell in the parent page whose left child points back | > | 2701 2702 2703 2704 2705 2706 2707 2708 2709 2710 2711 2712 2713 2714 2715 | pChild->idxParent = 0; pChild->isOverfull = 1; zeroPage(pPage, pChild->aData[0] & ~PTF_LEAF); put4byte(&pPage->aData[pPage->hdrOffset+6], pChild->pgno); pParent = pPage; pPage = pChild; extraUnref = pChild; TRACE(("BALANCE: Copy root into %d and blance\n", pPage->pgno)); } rc = sqlite3pager_write(pParent->aData); if( rc ) return rc; assert( pParent->isInit ); /* ** Find the cell in the parent page whose left child points back |
︙ | ︙ | |||
2830 2831 2832 2833 2834 2835 2836 2837 2838 2839 2840 2841 2842 2843 2844 2845 2846 2847 2848 2849 2850 2851 2852 2853 2854 2855 2856 2857 2858 2859 2860 2861 | reparentChildPages(pParent); /* ** balance the parent page. */ assert( pPage->isInit ); assert( pParent->isInit ); rc = balance(pParent); /* ** Cleanup before returning. */ balance_cleanup: for(i=0; i<nOld; i++){ releasePage(apOld[i]); if( apCopy[i] ){ sqliteFree(apCopy[i]->aCell); } } for(i=0; i<nNew; i++){ releasePage(apNew[i]); } releasePage(pParent); releasePage(extraUnref); 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 | > > | 2978 2979 2980 2981 2982 2983 2984 2985 2986 2987 2988 2989 2990 2991 2992 2993 2994 2995 2996 2997 2998 2999 3000 3001 3002 3003 3004 3005 3006 3007 3008 3009 3010 3011 | reparentChildPages(pParent); /* ** balance the parent page. */ assert( pPage->isInit ); assert( pParent->isInit ); pageIntegrity(pPage); rc = balance(pParent); /* ** Cleanup before returning. */ balance_cleanup: for(i=0; i<nOld; i++){ releasePage(apOld[i]); if( apCopy[i] ){ sqliteFree(apCopy[i]->aCell); } } for(i=0; i<nNew; i++){ releasePage(apNew[i]); } releasePage(pParent); releasePage(extraUnref); TRACE(("BALANCE: Finished with %d\n", pPage->pgno)); 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 |
︙ | ︙ | |||
3220 3221 3222 3223 3224 3225 3226 | } 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; | | | > | 3370 3371 3372 3373 3374 3375 3376 3377 3378 3379 3380 3381 3382 3383 3384 3385 3386 | } 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 parent=%d\n", pgno, data[hdr], data[hdr+5], (pPage->isInit && pPage->pParent) ? pPage->pParent->pgno : 0); 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; |
︙ | ︙ | |||
3317 3318 3319 3320 3321 3322 3323 | ** 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. */ | | > > | 3468 3469 3470 3471 3472 3473 3474 3475 3476 3477 3478 3479 3480 3481 3482 3483 3484 3485 3486 | ** 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 sqlite3BtreeCursorInfo(BtCursor *pCur, int *aResult){ int cnt, idx; MemPage *pPage = pCur->pPage; pageIntegrity(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 src/btree.h.
︙ | ︙ | |||
9 10 11 12 13 14 15 | ** May you share freely, never taking more than you give. ** ************************************************************************* ** This header file defines the interface that the sqlite B-Tree file ** subsystem. See comments in the source code for a detailed description ** of what each interface routine does. ** | | | 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | ** May you share freely, never taking more than you give. ** ************************************************************************* ** This header file defines the interface that the sqlite B-Tree file ** subsystem. See comments in the source code for a detailed description ** of what each interface routine does. ** ** @(#) $Id: btree.h,v 1.42 2004/05/09 00:40:52 drh Exp $ */ #ifndef _BTREE_H_ #define _BTREE_H_ /* TODO: This definition is just included so other modules compile. It ** needs to be revisited. */ |
︙ | ︙ | |||
89 90 91 92 93 94 95 | int sqlite3BtreeData(BtCursor*, u32 offset, u32 amt, void*); int sqlite3BtreeKeyCompare(BtCursor *, const void *, int, int, int *); char *sqlite3BtreeIntegrityCheck(Btree*, int *aRoot, int nRoot); struct Pager *sqlite3BtreePager(Btree*); #ifdef SQLITE_TEST | | | 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | int sqlite3BtreeData(BtCursor*, u32 offset, u32 amt, void*); int sqlite3BtreeKeyCompare(BtCursor *, const void *, int, int, int *); char *sqlite3BtreeIntegrityCheck(Btree*, int *aRoot, int nRoot); struct Pager *sqlite3BtreePager(Btree*); #ifdef SQLITE_TEST int sqlite3BtreeCursorInfo(BtCursor*, int*); void sqlite3BtreeCursorList(Btree*); int sqlite3BtreeFlags(BtCursor*); int sqlite3BtreePageDump(Btree*, int, int recursive); #endif #endif /* _BTREE_H_ */ |
Changes to src/test3.c.
︙ | ︙ | |||
9 10 11 12 13 14 15 | ** May you share freely, never taking more than you give. ** ************************************************************************* ** Code for testing the btree.c module in SQLite. This code ** is not included in the SQLite library. It is used for automated ** testing of the SQLite library. ** | | | 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | ** May you share freely, never taking more than you give. ** ************************************************************************* ** Code for testing the btree.c module in SQLite. This code ** is not included in the SQLite library. It is used for automated ** testing of the SQLite library. ** ** $Id: test3.c,v 1.32 2004/05/09 00:40:52 drh Exp $ */ #include "sqliteInt.h" #include "pager.h" #include "btree.h" #include "tcl.h" #include <stdlib.h> #include <string.h> |
︙ | ︙ | |||
992 993 994 995 996 997 998 | sqlite3BtreeDataSize(pCur, &n2); sprintf(zBuf, "%d", (int)(n1+n2)); Tcl_AppendResult(interp, zBuf, 0); return SQLITE_OK; } /* | | | | | 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 | sqlite3BtreeDataSize(pCur, &n2); sprintf(zBuf, "%d", (int)(n1+n2)); Tcl_AppendResult(interp, zBuf, 0); return SQLITE_OK; } /* ** Usage: btree_cursor_info ID ** ** Return eight integers containing information about the entry the ** cursor is pointing to: ** ** aResult[0] = The page number ** aResult[1] = The entry number ** aResult[2] = Total number of entries on this page ** aResult[3] = Size of this entry ** 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 */ static int btree_cursor_info( void *NotUsed, Tcl_Interp *interp, /* The TCL interpreter that invoked this command */ int argc, /* Number of arguments */ const char **argv /* Text of each argument */ ){ BtCursor *pCur; int rc; int i, j; int aResult[8]; char zBuf[400]; if( argc!=2 ){ Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0], " ID\"", 0); return TCL_ERROR; } if( Tcl_GetInt(interp, argv[1], (int*)&pCur) ) return TCL_ERROR; rc = sqlite3BtreeCursorInfo(pCur, aResult); if( rc ){ Tcl_AppendResult(interp, errorName(rc), 0); return TCL_ERROR; } j = 0; for(i=0; i<sizeof(aResult)/sizeof(aResult[0]); i++){ sprintf(&zBuf[j]," %d", aResult[i]); |
︙ | ︙ | |||
1093 1094 1095 1096 1097 1098 1099 | { "btree_eof", (Tcl_CmdProc*)btree_eof }, { "btree_keysize", (Tcl_CmdProc*)btree_keysize }, { "btree_key", (Tcl_CmdProc*)btree_key }, { "btree_data", (Tcl_CmdProc*)btree_data }, { "btree_payload_size", (Tcl_CmdProc*)btree_payload_size }, { "btree_first", (Tcl_CmdProc*)btree_first }, { "btree_last", (Tcl_CmdProc*)btree_last }, | | | 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 | { "btree_eof", (Tcl_CmdProc*)btree_eof }, { "btree_keysize", (Tcl_CmdProc*)btree_keysize }, { "btree_key", (Tcl_CmdProc*)btree_key }, { "btree_data", (Tcl_CmdProc*)btree_data }, { "btree_payload_size", (Tcl_CmdProc*)btree_payload_size }, { "btree_first", (Tcl_CmdProc*)btree_first }, { "btree_last", (Tcl_CmdProc*)btree_last }, { "btree_cursor_info", (Tcl_CmdProc*)btree_cursor_info }, { "btree_cursor_list", (Tcl_CmdProc*)btree_cursor_list }, { "btree_integrity_check", (Tcl_CmdProc*)btree_integrity_check }, { "btree_breakpoint", (Tcl_CmdProc*)btree_breakpoint }, }; int i; for(i=0; i<sizeof(aCmd)/sizeof(aCmd[0]); i++){ Tcl_CreateCommand(interp, aCmd[i].zName, aCmd[i].xProc, 0, 0); } Tcl_LinkVar(interp, "pager_refinfo_enable", (char*)&pager3_refinfo_enable, TCL_LINK_INT); return TCL_OK; } |
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.21 2004/05/09 00:40:52 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl # Basic functionality. Open and close a database. # |
︙ | ︙ | |||
530 531 532 533 534 535 536 | # Totals 1016 bytes. 8 bytes left over # Keys are 1000 through 1090. for {set i 1000} {$i<1091} {incr i} { set key $i set data [format %5d $i] btree_insert $::c1 $key $data } | | | | | | | | | | | | | > | | 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 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 625 626 627 628 629 630 631 632 633 | # Totals 1016 bytes. 8 bytes left over # Keys are 1000 through 1090. for {set i 1000} {$i<1091} {incr i} { set key $i set data [format %5d $i] btree_insert $::c1 $key $data } lrange [btree_cursor_info $::c1] 4 5 } {8 1} do_test btree-7.3 { for {set i 1001} {$i<1091} {incr i 2} { btree_move_to $::c1 $i btree_delete $::c1 } # Freed 45 blocks. Total freespace is 458 # Keys remaining are even numbers between 1000 and 1090, inclusive lrange [btree_cursor_info $::c1] 4 5 } {458 46} #btree_tree_dump $::b1 1 do_test btree-7.4 { # The largest free block is 10 bytes long. So if we insert # a record bigger than 10 bytes it should force a defrag # The record is 20 bytes long. btree_insert $::c1 2000 {123456789_12345} btree_move_to $::c1 2000 btree_key $::c1 } {2000} do_test btree-7.5 { lrange [btree_cursor_info $::c1] 4 5 } {438 1} #btree_tree_dump $::b1 1 # Delete an entry to make a hole of a known size, then immediately recreate # that entry. This tests the path into allocateSpace where the hole exactly # matches the size of the desired space. # # Keys are even numbers between 1000 and 1090 and one record of 2000. # There are 47 keys total. # do_test btree-7.6 { btree_move_to $::c1 1006 btree_delete $::c1 btree_move_to $::c1 1010 btree_delete $::c1 } {} do_test btree-7.7 { lrange [btree_cursor_info $::c1] 4 5 } {458 3} ;# Create two new holes of 10 bytes each #btree_page_dump $::b1 2 do_test btree-7.8 { btree_insert $::c1 1006 { 1006} lrange [btree_cursor_info $::c1] 4 5 } {448 2} ;# Filled in the first hole #btree_page_dump $::b1 2 # Make sure the freeSpace() routine properly coaleses adjacent memory blocks # do_test btree-7.9 { btree_move_to $::c1 1012 btree_delete $::c1 lrange [btree_cursor_info $::c1] 4 5 } {458 2} ;# Coalesce with the whole before do_test btree-7.10 { btree_move_to $::c1 1008 btree_delete $::c1 lrange [btree_cursor_info $::c1] 4 5 } {468 2} ;# Coalesce with whole after do_test btree-7.11 { btree_move_to $::c1 1030 btree_delete $::c1 lrange [btree_cursor_info $::c1] 4 5 } {478 3} ;# Make a new hole do_test btree-7.13 { btree_move_to $::c1 1034 btree_delete $::c1 lrange [btree_cursor_info $::c1] 4 5 } {488 4} ;# Make another hole do_test btree-7.14 { btree_move_to $::c1 1032 btree_delete $::c1 lrange [btree_cursor_info $::c1] 4 5 } {498 3} ;# The freed space should coalesce on both ends #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. # #btree_page_dump $::b1 1 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 do_test btree-8.1.1 { lindex [btree_pager_stats $::b1] 1 } {1} #btree_pager_ref_dump $::b1 do_test btree-8.2 { btree_move_to $::c1 2020 string length [btree_data $::c1] |
︙ | ︙ | |||
753 754 755 756 757 758 759 | #btree_tree_dump $::b1 2 #btree_pager_ref_dump $::b1 #set pager_refinfo_enable 1 do_test btree-9.2 { btree_insert $::c1 020 {*** 020 *** 020 *** 020 *** 020 ***} select_keys $::c1 } {001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020} | < < | 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 | #btree_tree_dump $::b1 2 #btree_pager_ref_dump $::b1 #set pager_refinfo_enable 1 do_test btree-9.2 { btree_insert $::c1 020 {*** 020 *** 020 *** 020 *** 020 ***} select_keys $::c1 } {001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020} #btree_page_dump $::b1 2 #btree_pager_ref_dump $::b1 #set pager_refinfo_enable 0 # The previous "select_keys" command left the cursor pointing at the root # page. So there should only be two pages checked out. 2 (the root) and # page 1. do_test btree-9.2.1 { |
︙ | ︙ | |||
856 857 858 859 860 861 862 | #btree_tree_dump $::b1 2 } # Create a tree with lots more pages # catch {unset ::data} catch {unset ::key} | | < < < < < < < < < < < < | 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 | #btree_tree_dump $::b1 2 } # Create a tree with lots more pages # catch {unset ::data} catch {unset ::key} for {set i 31} {$i<=999} {incr i} { do_test btree-11.1.$i.1 { set key [format %03d $i] set ::data "*** $key *** $key *** $key *** $key ***" btree_insert $::c1 $key $data btree_move_to $::c1 $key btree_key $::c1 } [format %03d $i] do_test btree-11.1.$i.2 { btree_data $::c1 } $::data set ::key [format %03d [expr {$i/2}]] if {$::key=="012"} {set ::key 013} do_test btree-11.1.$i.3 { btree_move_to $::c1 $::key |
︙ | ︙ | |||
904 905 906 907 908 909 910 | lindex [btree_pager_stats $::b1] 1 } {2} #btree_page_dump $::b1 2 # Delete the dividers on the root page # do_test btree-11.4 { | | < < < < | | < < < < < < < < < < < < < | < < < | > | < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < > > > | 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 | lindex [btree_pager_stats $::b1] 1 } {2} #btree_page_dump $::b1 2 # Delete the dividers on the root page # do_test btree-11.4 { btree_move_to $::c1 551 btree_delete $::c1 btree_move_to $::c1 551 set k [btree_key $::c1] if {$k==550} { set k [btree_next $::c1] } btree_key $::c1 } {552} # Change the data on an intermediate node such that the node becomes overfull # and has to split. We happen to know that intermediate nodes exist on # 337, 401 and 465 by the btree_page_dumps above # catch {unset ::data} set ::data {This is going to be a very long data segment} append ::data $::data append ::data $::data do_test btree-12.1 { btree_insert $::c1 337 $::data btree_move_to $::c1 337 btree_data $::c1 } $::data do_test btree-12.2 { btree_insert $::c1 401 $::data btree_move_to $::c1 401 btree_data $::c1 } $::data do_test btree-12.3 { btree_insert $::c1 465 $::data btree_move_to $::c1 465 btree_data $::c1 } $::data do_test btree-12.4 { btree_move_to $::c1 337 btree_key $::c1 } {337} do_test btree-12.5 { |
︙ | ︙ | |||
1030 1031 1032 1033 1034 1035 1036 | btree_next $::c1 btree_data $::c1 } $::data do_test btree-12.12 { btree_next $::c1 btree_key $::c1 } {402} | | | | | 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 | btree_next $::c1 btree_data $::c1 } $::data do_test btree-12.12 { btree_next $::c1 btree_key $::c1 } {402} #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 |
︙ | ︙ |
Changes to test/btree2.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: btree2.test,v 1.11 2004/05/09 00:40:52 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl if {[info commands btree_open]!=""} { |
︙ | ︙ | |||
349 350 351 352 353 354 355 | set ::c4 [btree_cursor $::b 4 1] set ::c5 [btree_cursor $::b 5 1] set ::c6 [btree_cursor $::b 6 1] check_invariants } {} set cnt 6 for {set i 2} {$i<=6} {incr i} { | | | 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 | set ::c4 [btree_cursor $::b 4 1] set ::c5 [btree_cursor $::b 5 1] set ::c6 [btree_cursor $::b 6 1] check_invariants } {} set cnt 6 for {set i 2} {$i<=6} {incr i} { if {[lindex [btree_cursor_info [set ::c$i]] 0]!=$i} {incr cnt} } do_test $testid.1 { btree_begin_transaction $::b lindex [btree_pager_stats $::b] 1 } $cnt # exec cp test2.bt test2.bt.bu1 do_test $testid.2 [subst { |
︙ | ︙ |