Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | More btree.c bug fixes. (CVS 1327) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
e9f84ff3fe45a014ab60fabbfd91d19e |
User & Date: | drh 2004-05-08 20:07:40.000 |
Context
2004-05-09
| ||
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) | |
10:56 | Get the code back to the point where it will compile the btree.c tests. Move the default key comparison routine from btree.c into vdbeaux.c. Commented out code in vdbe.c that will need to be fixed. (CVS 1326) (check-in: 2bca92240b 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.116 2004/05/08 20:07:40 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. |
︙ | ︙ | |||
207 208 209 210 211 212 213 | ** The pParent field points back to the parent page. This allows us to ** walk up the BTree from any leaf to the root. Care must be taken to ** unref() the parent page pointer when this page is no longer referenced. ** The pageDestructor() routine handles that chore. */ struct MemPage { u32 notUsed; | < < < < > > > > > | 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 | ** The pParent field points back to the parent page. This allows us to ** walk up the BTree from any leaf to the root. Care must be taken to ** unref() the parent page pointer when this page is no longer referenced. ** The pageDestructor() routine handles that chore. */ struct MemPage { u32 notUsed; 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 */ unsigned char *aData; /* Pointer back to the start of the page */ Pgno pgno; /* Page number for this page */ MemPage *pParent; /* The parent of this page. NULL for root */ }; /* ** The in-memory image of a disk page has the auxiliary information appended ** to the end. EXTRA_SIZE is the number of bytes of space needed to hold ** that extra information. */ |
︙ | ︙ | |||
594 595 596 597 598 599 600 | 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->pParent==0 || pPage->pParent==pParent ); if( pPage->pParent==0 && pParent!=0 ){ pPage->pParent = pParent; sqlite3pager_ref(pParent->aData); } if( pPage->isInit ) return SQLITE_OK; 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; if( pPage->nCell>pageSize ) return SQLITE_CORRUPT; |
︙ | ︙ | |||
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 | */ 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){ | > > > > > | 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 695 696 697 698 | */ static void zeroPage(MemPage *pPage, int flags){ unsigned char *data = pPage->aData; Btree *pBt = pPage->pBt; int hdr = pPage->hdrOffset; int first; assert( sqlite3pager_pagenumber(data)==pPage->pgno ); assert( &data[pBt->pageSize] == (unsigned char*)pPage ); 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; 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){ |
︙ | ︙ | |||
997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 | 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. ** | > > > > > > > > > > > > > > > > > > | 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 | releasePage(pPage); pCur->pPage = 0; pCur->isValid = 0; pCur->status = SQLITE_ABORT; } } } #ifdef SQLITE_TEST /* ** Print debugging information about all cursors to standard output. */ void sqlite3BtreeCursorList(Btree *pBt){ BtCursor *pCur; for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){ MemPage *pPage = pCur->pPage; char *zMode = pCur->wrFlag ? "rw" : "ro"; printf("CURSOR %08x rooted at %4d(%s) currently at %d.%d%s\n", (int)pCur, pCur->pgnoRoot, zMode, pPage ? pPage->pgno : 0, pCur->idx, pCur->isValid ? "" : " eof" ); } } #endif /* ** 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. ** |
︙ | ︙ | |||
1532 1533 1534 1535 1536 1537 1538 | ** 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; | | | > | 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 | ** 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; if( pParent==0 ) return 1; if( pParent->pgno>1 ) return 0; if( get2byte(&pParent->aData[pParent->hdrOffset+3])==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 |
︙ | ︙ | |||
2306 2307 2308 2309 2310 2311 2312 2313 2314 2315 2316 2317 2318 2319 2320 | assert( idx>pPage->hdrOffset && idx<pPage->pBt->pageSize ); put2byte(&pPage->aData[idxFrom], idx); idxFrom = idx; } put2byte(&pPage->aData[idxFrom], 0); } /* ** 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. */ | > > > > > > > > | | | > | > | 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 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 | 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 movePage(MemPage *pTo, MemPage *pFrom){ uptr from, to; int i; int pageSize; int ofst; assert( pTo->hdrOffset==0 ); ofst = pFrom->hdrOffset; pageSize = pFrom->pBt->pageSize; sqliteFree(pTo->aCell); memcpy(pTo->aData, &pFrom->aData[ofst], pageSize - ofst); memcpy(pTo, pFrom, offsetof(MemPage, aData)); pFrom->isInit = 0; pFrom->aCell = 0; assert( pTo->aData[5]<155 ); pTo->aData[5] += ofst; pTo->isOverfull = pFrom->isOverfull; to = Addr(pTo->aData); from = Addr(&pFrom->aData[ofst]); for(i=0; i<pTo->nCell; i++){ uptr x = Addr(pTo->aCell[i]); |
︙ | ︙ | |||
2404 2405 2406 2407 2408 2409 2410 2411 2412 2413 2414 2415 2416 2417 | 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 */ | > | 2440 2441 2442 2443 2444 2445 2446 2447 2448 2449 2450 2451 2452 2453 2454 | 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 *extraUnref = 0; /* Unref this page if not zero */ 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 */ |
︙ | ︙ | |||
2506 2507 2508 2509 2510 2511 2512 | ** 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) ); | | > < > | > | 2543 2544 2545 2546 2547 2548 2549 2550 2551 2552 2553 2554 2555 2556 2557 2558 2559 2560 2561 2562 2563 2564 2565 2566 2567 | ** 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) ); movePage(pChild, pPage); assert( pChild->aData[0]==pPage->aData[pPage->hdrOffset] ); pChild->pParent = pPage; sqlite3pager_ref(pPage->aData); 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 |
︙ | ︙ | |||
2589 2590 2591 2592 2593 2594 2595 | /* ** Make copies of the content of pPage and its siblings into aOld[]. ** 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++){ | | < | > > | | 2628 2629 2630 2631 2632 2633 2634 2635 2636 2637 2638 2639 2640 2641 2642 2643 2644 2645 2646 | /* ** Make copies of the content of pPage and its siblings into aOld[]. ** 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]; p->aCell = 0; p->hdrOffset = 0; movePage(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. ** |
︙ | ︙ | |||
2617 2618 2619 2620 2621 2622 2623 | 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 ){ | | | > | | 2657 2658 2659 2660 2661 2662 2663 2664 2665 2666 2667 2668 2669 2670 2671 2672 2673 2674 2675 2676 | 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]); memcpy(aTemp[i], apDiv[i], szCell[nCell]); apCell[nCell] = &aTemp[i][leafCorrection]; dropCell(pParent, nxDiv, szCell[nCell]); szCell[nCell] -= leafCorrection; assert( get4byte(&aTemp[i][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 ); |
︙ | ︙ | |||
2673 2674 2675 2676 2677 2678 2679 2680 | /* ** 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 ){ | > | | | > | < | | 2714 2715 2716 2717 2718 2719 2720 2721 2722 2723 2724 2725 2726 2727 2728 2729 2730 2731 2732 2733 2734 2735 2736 2737 2738 2739 2740 2741 2742 2743 2744 2745 2746 2747 2748 | /* ** Allocate k new pages. Reuse old pages where possible. */ assert( pPage->pgno>1 ); pageFlags = pPage->aData[0]; for(i=0; i<k; i++){ MemPage *pNew; if( i<nOld ){ pNew = apNew[i] = apOld[i]; pgnoNew[i] = pgnoOld[i]; apOld[i] = 0; sqlite3pager_write(pNew->aData); }else{ rc = allocatePage(pBt, &pNew, &pgnoNew[i], pgnoNew[i-1]); if( rc ) goto balance_cleanup; apNew[i] = pNew; } nNew++; zeroPage(pNew, pageFlags); } /* Free any old pages that were not reused as new pages. */ while( i<nOld ){ rc = freePage(apOld[i]); if( rc ) goto balance_cleanup; releasePage(apOld[i]); 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 |
︙ | ︙ | |||
2786 2787 2788 2789 2790 2791 2792 2793 2794 2795 2796 2797 2798 2799 2800 2801 | 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] ){ | > > > < > | 2828 2829 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(apNew[i]); } 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 |
︙ | ︙ | |||
2954 2955 2956 2957 2958 2959 2960 2961 2962 2963 2964 2965 2966 2967 2968 2969 2970 2971 | ** 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); | > | > > | 2999 3000 3001 3002 3003 3004 3005 3006 3007 3008 3009 3010 3011 3012 3013 3014 3015 3016 3017 3018 3019 3020 3021 3022 3023 3024 3025 3026 3027 3028 3029 3030 | ** 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; unsigned char tempbuf[4]; 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); memcpy(tempbuf, &pNext[-2], 4); put4byte(&pNext[-2], pgnoChild); insertCell(pPage, pCur->idx, &pNext[-4], szNext+4); rc = balance(pPage); if( rc ) return rc; memcpy(&pNext[-2], tempbuf, 4); dropCell(leafCur.pPage, leafCur.idx, szNext); rc = balance(leafCur.pPage); releaseTempCursor(&leafCur); }else{ dropCell(pPage, pCur->idx, cellSize(pPage, pCell)); rc = balance(pPage); } |
︙ | ︙ | |||
3154 3155 3156 3157 3158 3159 3160 | ** Print a disassembly of the given page on standard output. This routine ** is used for debugging and testing only. */ #ifdef SQLITE_TEST int sqlite3BtreePageDump(Btree *pBt, int pgno, int recursive){ int rc; MemPage *pPage; | | > > > > | 3202 3203 3204 3205 3206 3207 3208 3209 3210 3211 3212 3213 3214 3215 3216 3217 3218 3219 3220 3221 3222 3223 3224 3225 3226 3227 3228 3229 3230 3231 3232 3233 | ** Print a disassembly of the given page on standard output. This routine ** is used for debugging and testing only. */ #ifdef SQLITE_TEST int sqlite3BtreePageDump(Btree *pBt, int pgno, int recursive){ int rc; MemPage *pPage; int i, j, c; int nFree; u16 idx; int hdr; unsigned char *data; char range[20]; unsigned char payload[20]; rc = getPage(pBt, (Pgno)pgno, &pPage); if( rc ){ return rc; } 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; |
︙ | ︙ |
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.41 2004/05/08 20:07:40 drh Exp $ */ #ifndef _BTREE_H_ #define _BTREE_H_ /* TODO: This definition is just included so other modules compile. It ** needs to be revisited. */ |
︙ | ︙ | |||
90 91 92 93 94 95 96 97 98 99 100 101 102 | int sqlite3BtreeKeyCompare(BtCursor *, const void *, int, int, int *); char *sqlite3BtreeIntegrityCheck(Btree*, int *aRoot, int nRoot); struct Pager *sqlite3BtreePager(Btree*); #ifdef SQLITE_TEST int sqlite3BtreeCursorDump(BtCursor*, int*); int sqlite3BtreeFlags(BtCursor*); int sqlite3BtreePageDump(Btree*, int, int recursive); #endif #endif /* _BTREE_H_ */ | > < < < | 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | int sqlite3BtreeKeyCompare(BtCursor *, const void *, int, int, int *); char *sqlite3BtreeIntegrityCheck(Btree*, int *aRoot, int nRoot); struct Pager *sqlite3BtreePager(Btree*); #ifdef SQLITE_TEST int sqlite3BtreeCursorDump(BtCursor*, int*); void sqlite3BtreeCursorList(Btree*); int sqlite3BtreeFlags(BtCursor*); int sqlite3BtreePageDump(Btree*, int, int recursive); #endif #endif /* _BTREE_H_ */ |
Changes to src/pager.c.
︙ | ︙ | |||
14 15 16 17 18 19 20 | ** The pager is used to access a database disk file. It implements ** atomic commit and rollback through the use of a journal file that ** is separate from the database file. The pager also implements file ** locking to prevent two processes from writing the same database ** file simultaneously, or one process from reading the database while ** another is writing. ** | | | 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | ** The pager is used to access a database disk file. It implements ** atomic commit and rollback through the use of a journal file that ** is separate from the database file. The pager also implements file ** locking to prevent two processes from writing the same database ** file simultaneously, or one process from reading the database while ** another is writing. ** ** @(#) $Id: pager.c,v 1.105 2004/05/08 20:07:40 drh Exp $ */ #include "os.h" /* Must be first to enable large file support */ #include "sqliteInt.h" #include "pager.h" #include <assert.h> #include <string.h> |
︙ | ︙ | |||
1111 1112 1113 1114 1115 1116 1117 | */ Pgno sqlite3pager_pagenumber(void *pData){ PgHdr *p = DATA_TO_PGHDR(pData); return p->pgno; } /* | | | > > > > < | 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 | */ Pgno sqlite3pager_pagenumber(void *pData){ PgHdr *p = DATA_TO_PGHDR(pData); return p->pgno; } /* ** The page_ref() function increments the reference count for a page. ** If the page is currently on the freelist (the reference count is zero) then ** remove it from the freelist. ** ** For non-test systems, page_ref() is a macro that calls _page_ref() ** online of the reference count is zero. For test systems, page_ref() ** is a real function so that we can set breakpoints and trace it. */ static void _page_ref(PgHdr *pPg){ if( pPg->nRef==0 ){ /* The page is currently on the freelist. Remove it. */ if( pPg==pPg->pPager->pFirstSynced ){ PgHdr *p = pPg->pNextFree; while( p && p->needSync ){ p = p->pNextFree; } pPg->pPager->pFirstSynced = p; |
︙ | ︙ | |||
1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 | pPg->pPager->pLast = pPg->pPrevFree; } pPg->pPager->nRef++; } pPg->nRef++; REFINFO(pPg); } /* ** Increment the reference count for a page. The input pointer is ** a reference to the page data. */ int sqlite3pager_ref(void *pData){ PgHdr *pPg = DATA_TO_PGHDR(pData); | > > > > > > > > > > > > | 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 | pPg->pPager->pLast = pPg->pPrevFree; } pPg->pPager->nRef++; } pPg->nRef++; REFINFO(pPg); } #ifdef SQLITE_TEST static void page_ref(PgHdr *pPg){ if( pPg->nRef==0 ){ _page_ref(pPg); }else{ pPg->nRef++; REFINFO(pPg); } } #else # define page_ref(P) ((P)->nRef==0?_page_ref(P):(void)(P)->nRef++) #endif /* ** Increment the reference count for a page. The input pointer is ** a reference to the page data. */ int sqlite3pager_ref(void *pData){ PgHdr *pPg = DATA_TO_PGHDR(pData); |
︙ | ︙ | |||
2216 2217 2218 2219 2220 2221 2222 | for(pPg=pPager->pAll; pPg; pPg=pPg->pNextAll){ if( pPg->nRef<=0 ) continue; printf("PAGE %3d addr=0x%08x nRef=%d\n", pPg->pgno, (int)PGHDR_TO_DATA(pPg), pPg->nRef); } } #endif | < < < | 2231 2232 2233 2234 2235 2236 2237 | for(pPg=pPager->pAll; pPg; pPg=pPg->pNextAll){ if( pPg->nRef<=0 ) continue; printf("PAGE %3d addr=0x%08x nRef=%d\n", pPg->pgno, (int)PGHDR_TO_DATA(pPg), pPg->nRef); } } #endif |
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.31 2004/05/08 20:07:40 drh Exp $ */ #include "sqliteInt.h" #include "pager.h" #include "btree.h" #include "tcl.h" #include <stdlib.h> #include <string.h> |
︙ | ︙ | |||
503 504 505 506 507 508 509 510 511 512 513 514 515 516 | zResult = sqlite3BtreeIntegrityCheck(pBt, aRoot, nRoot); if( zResult ){ Tcl_AppendResult(interp, zResult, 0); sqliteFree(zResult); } return TCL_OK; } /* ** Usage: btree_cursor ID TABLENUM WRITEABLE ** ** Create a new cursor. Return the ID for the cursor. */ static int btree_cursor( | > > > > > > > > > > > > > > > > > > > > > > > | 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 | zResult = sqlite3BtreeIntegrityCheck(pBt, aRoot, nRoot); if( zResult ){ Tcl_AppendResult(interp, zResult, 0); sqliteFree(zResult); } return TCL_OK; } /* ** Usage: btree_cursor_list ID ** ** Print information about all cursors to standard output for debugging. */ static int btree_cursor_list( void *NotUsed, Tcl_Interp *interp, /* The TCL interpreter that invoked this command */ int argc, /* Number of arguments */ const char **argv /* Text of each argument */ ){ Btree *pBt; if( argc!=2 ){ Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0], " ID\"", 0); return TCL_ERROR; } if( Tcl_GetInt(interp, argv[1], (int*)&pBt) ) return TCL_ERROR; sqlite3BtreeCursorList(pBt); return SQLITE_OK; } /* ** Usage: btree_cursor ID TABLENUM WRITEABLE ** ** Create a new cursor. Return the ID for the cursor. */ static int btree_cursor( |
︙ | ︙ | |||
1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 | { "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_dump", (Tcl_CmdProc*)btree_cursor_dump }, { "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; } | > < < < | 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 | { "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_dump", (Tcl_CmdProc*)btree_cursor_dump }, { "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.20 2004/05/08 20:07:40 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl # Basic functionality. Open and close a database. # |
︙ | ︙ | |||
823 824 825 826 827 828 829 | lindex [btree_pager_stats $::b1] 1 } {1} do_test btree-10.2 { set ::c1 [btree_cursor $::b1 2 1] lindex [btree_pager_stats $::b1] 1 } {2} do_test btree-10.3 { | | | < | < > > > | | < > | > > | | > > > > > > > > > > > > > | | 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 | lindex [btree_pager_stats $::b1] 1 } {1} do_test btree-10.2 { set ::c1 [btree_cursor $::b1 2 1] lindex [btree_pager_stats $::b1] 1 } {2} do_test btree-10.3 { for {set i 1} {$i<=30} {incr i} { set key [format %03d $i] set data "*** $key *** $key *** $key *** $key ***" btree_insert $::c1 $key $data } select_keys $::c1 } {001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030} #btree_tree_dump $::b1 2 do_test btree-10.4 { # The divider entry is 012. This is found by uncommenting the # btree_tree_dump call above and looking at the tree. If the page size # changes, this test will no longer work. btree_move_to $::c1 012 btree_delete $::c1 select_keys $::c1 } {001 002 003 004 005 006 007 008 009 010 011 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030} #btree_pager_ref_dump $::b1 #btree_tree_dump $::b1 2 for {set i 1} {$i<=30} {incr i} { # Check the number of unreference pages. This should be 3 in most cases, # but 2 when the cursor is pointing to the divider entry which is now 013. do_test btree-10.5.$i { btree_move_to $::c1 [format %03d $i] lindex [btree_pager_stats $::b1] 1 } [expr {$i==13?2:3}] #btree_pager_ref_dump $::b1 #btree_tree_dump $::b1 2 } # Create a tree with lots more pages # catch {unset ::data} catch {unset ::key} for {set i 31} {$i<=1000} {incr i} { if {$i==88} { set pager_refinfo_enable 1 btree_tree_dump $b1 2 btree_pager_ref_dump $b1 btree_cursor_list $b1 } 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] if {$i==88} { btree_pager_ref_dump $b1 btree_cursor_list $b1 btree_tree_dump $b1 2 exit } 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 btree_key $::c1 } $::key } catch {unset ::data} catch {unset ::key} |
︙ | ︙ |