Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | More btree.c bug fixing. It's getting closer but still not there yet. Move obsolete test scripts into the attic. (CVS 1331) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
9379c7c9cf8b0770a0c8d1feb5ffdba3 |
User & Date: | drh 2004-05-09 20:40:11.000 |
Context
2004-05-09
| ||
23:23 | Add a temporary sqlite2BtreeKeyCompare() function to help get regression tests passing again. (CVS 1332) (check-in: d8d1c91e55 user: danielk1977 tags: trunk) | |
20:40 | More btree.c bug fixing. It's getting closer but still not there yet. Move obsolete test scripts into the attic. (CVS 1331) (check-in: 9379c7c9cf user: drh tags: trunk) | |
11:51 | The btree.test test is no working with integrity_check enabled. (CVS 1330) (check-in: 9f1caa530e 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.120 2004/05/09 20:40:11 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. |
︙ | ︙ | |||
887 888 889 890 891 892 893 | return rc; } sqlite3pager_set_destructor(pBt->pPager, pageDestructor); pBt->pCursor = 0; pBt->pPage1 = 0; pBt->readOnly = sqlite3pager_isreadonly(pBt->pPager); pBt->pageSize = SQLITE_PAGE_SIZE; /* FIX ME - read from header */ | > > > > > > > > > > > | > | 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 | return rc; } sqlite3pager_set_destructor(pBt->pPager, pageDestructor); pBt->pCursor = 0; pBt->pPage1 = 0; pBt->readOnly = sqlite3pager_isreadonly(pBt->pPager); pBt->pageSize = SQLITE_PAGE_SIZE; /* FIX ME - read from header */ /* maxLocal is the maximum amount of payload to store locally for ** a cell. Make sure it is small enough so that at least MN_CELLS_PER_PAGE ** will fit on one page. We assume a 10-byte page header. Besides ** the payload, the cell must store: ** 2-byte pointer to next cell ** 4-byte child pointer ** 9-byte nKey value ** 4-byte nData value ** 4-byte overflow page pointer */ pBt->maxLocal = (pBt->pageSize-10)/MN_CELLS_PER_PAGE - 23; assert( pBt->maxLocal + 23 <= MX_CELL_SIZE ); *ppBtree = pBt; return SQLITE_OK; } /* ** Close an open database and invalidate all cursors. */ |
︙ | ︙ | |||
2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 | pCur->idx--; rc = SQLITE_OK; } *pRes = 0; return rc; } /* ** Allocate a new page from the database file. ** ** The new page is marked as dirty. (In other words, sqlite3pager_write() ** has already been called on the new page.) The new page has also ** been referenced and the calling routine is responsible for calling ** sqlite3pager_unref() on the new page when it is done. | > > > > > > > > > > > > | 2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060 2061 | pCur->idx--; rc = SQLITE_OK; } *pRes = 0; return rc; } /* ** The TRACE macro will print high-level status information about the ** btree operation when the global variable sqlite3_btree_trace is ** enabled. */ #if SQLITE_TEST # define TRACE(X) if( sqlite3_btree_trace ){ printf X; fflush(stdout); } #else # define TRACE(X) #endif int sqlite3_btree_trace=0; /* True to enable tracing */ /* ** Allocate a new page from the database file. ** ** The new page is marked as dirty. (In other words, sqlite3pager_write() ** has already been called on the new page.) The new page has also ** been referenced and the calling routine is responsible for calling ** sqlite3pager_unref() on the new page when it is done. |
︙ | ︙ | |||
2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 | k = get4byte(&pTrunk->aData[4]); if( k==0 ){ /* The trunk has no leaves. So extract the trunk page itself and ** use it as the newly allocated page */ *pPgno = get4byte(&pPage1->aData[32]); memcpy(&pPage1->aData[32], &pTrunk->aData[0], 4); *ppPage = pTrunk; }else{ /* Extract a leaf from the trunk */ int closest; unsigned char *aData = pTrunk->aData; if( nearby>0 ){ int i, dist; closest = 0; dist = get4byte(&aData[8]) - nearby; if( dist<0 ) dist = -dist; | > | < > > | > | 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104 2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 | k = get4byte(&pTrunk->aData[4]); if( k==0 ){ /* The trunk has no leaves. So extract the trunk page itself and ** use it as the newly allocated page */ *pPgno = get4byte(&pPage1->aData[32]); memcpy(&pPage1->aData[32], &pTrunk->aData[0], 4); *ppPage = pTrunk; TRACE(("ALLOCATE: %d trunk - %d free pages left\n", *pPgno, n-1)); }else{ /* Extract a leaf from the trunk */ int closest; unsigned char *aData = pTrunk->aData; if( nearby>0 ){ int i, dist; closest = 0; dist = get4byte(&aData[8]) - nearby; if( dist<0 ) dist = -dist; for(i=1; i<k; i++){ int d2 = get4byte(&aData[8+i*4]) - nearby; if( d2<0 ) d2 = -d2; if( d2<dist ) closest = i; } }else{ closest = 0; } *pPgno = get4byte(&aData[8+closest*4]); TRACE(("ALLOCATE: %d was leaf %d of %d on trunk %d: %d more free pages\n", *pPgno, closest+1, k, pTrunk->pgno, n-1)); if( closest<k-1 ){ memcpy(&aData[8+closest*4], &aData[4+k*4], 4); } put4byte(&aData[4], k-1); rc = getPage(pBt, *pPgno, ppPage); releasePage(pTrunk); if( rc==SQLITE_OK ){ sqlite3pager_dont_rollback((*ppPage)->aData); rc = sqlite3pager_write((*ppPage)->aData); } } }else{ /* There are no pages on the freelist, so create a new page at the ** end of the file */ *pPgno = sqlite3pager_pagecount(pBt->pPager) + 1; rc = getPage(pBt, *pPgno, ppPage); if( rc ) return rc; rc = sqlite3pager_write((*ppPage)->aData); TRACE(("ALLOCATE: %d from end of file\n", *pPgno)); } return rc; } /* ** Add a page of the database file to the freelist. ** |
︙ | ︙ | |||
2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 | if( n==0 ){ /* This is the first free page */ rc = sqlite3pager_write(pPage->aData); if( rc ) return rc; memset(pPage->aData, 0, 8); put4byte(&pPage1->aData[32], pPage->pgno); }else{ /* Other free pages already exist. Retrive the first trunk page ** of the freelist and find out how many leaves it has. */ MemPage *pTrunk; rc = getPage(pBt, get4byte(&pPage1->aData[32]), &pTrunk); if( rc ) return rc; k = get4byte(&pTrunk->aData[4]); if( k==pBt->pageSize/4 - 8 ){ /* The trunk is full. Turn the page being freed into a new ** trunk page with no leaves. */ rc = sqlite3pager_write(pPage->aData); if( rc ) return rc; put4byte(pPage->aData, pTrunk->pgno); put4byte(&pPage->aData[4], 0); put4byte(&pPage1->aData[32], pPage->pgno); }else{ /* Add the newly freed page as a leaf on the current trunk */ rc = sqlite3pager_write(pTrunk->aData); if( rc ) return rc; put4byte(&pTrunk->aData[4], k+1); put4byte(&pTrunk->aData[8+k*4], pPage->pgno); sqlite3pager_dont_write(pBt->pPager, pPage->pgno); } releasePage(pTrunk); } return rc; } /* | > > > > | 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 | if( n==0 ){ /* This is the first free page */ rc = sqlite3pager_write(pPage->aData); if( rc ) return rc; memset(pPage->aData, 0, 8); put4byte(&pPage1->aData[32], pPage->pgno); TRACE(("FREE-PAGE: %d first\n", pPage->pgno)); }else{ /* Other free pages already exist. Retrive the first trunk page ** of the freelist and find out how many leaves it has. */ MemPage *pTrunk; rc = getPage(pBt, get4byte(&pPage1->aData[32]), &pTrunk); if( rc ) return rc; k = get4byte(&pTrunk->aData[4]); if( k==pBt->pageSize/4 - 8 ){ /* The trunk is full. Turn the page being freed into a new ** trunk page with no leaves. */ rc = sqlite3pager_write(pPage->aData); if( rc ) return rc; put4byte(pPage->aData, pTrunk->pgno); put4byte(&pPage->aData[4], 0); put4byte(&pPage1->aData[32], pPage->pgno); TRACE(("FREE-PAGE: %d new trunk page replacing %d\n", pPage->pgno, pTrunk->pgno)); }else{ /* Add the newly freed page as a leaf on the current trunk */ rc = sqlite3pager_write(pTrunk->aData); if( rc ) return rc; put4byte(&pTrunk->aData[4], k+1); put4byte(&pTrunk->aData[8+k*4], pPage->pgno); sqlite3pager_dont_write(pBt->pPager, pPage->pgno); TRACE(("FREE-PAGE: %d leaf on trunk page %d\n",pPage->pgno,pTrunk->pgno)); } releasePage(pTrunk); } return rc; } /* |
︙ | ︙ | |||
2365 2366 2367 2368 2369 2370 2371 | 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 ); | | | 2396 2397 2398 2399 2400 2401 2402 2403 2404 2405 2406 2407 2408 2409 2410 | 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]; } |
︙ | ︙ | |||
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 | 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]); if( x>from && x<from+pageSize-ofst ){ *((uptr*)&pTo->aCell[i]) = x + to - from; } } } | > < < < < < < < < < | 2520 2521 2522 2523 2524 2525 2526 2527 2528 2529 2530 2531 2532 2533 2534 2535 2536 2537 2538 2539 2540 2541 2542 2543 2544 2545 2546 2547 2548 2549 2550 2551 2552 2553 2554 | static void movePage(MemPage *pTo, MemPage *pFrom){ uptr from, to; int i; int pageSize; int ofst; assert( pTo->hdrOffset==0 ); assert( pFrom->isInit ); 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]); 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. ** |
︙ | ︙ | |||
2602 2603 2604 2605 2606 2607 2608 2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619 2620 | int szCell[(MX_CELL+2)*NB]; /* Local size of all cells */ u8 aCopy[NB][MX_PAGE_SIZE+sizeof(MemPage)]; /* Space for apCopy[] */ /* ** Return without doing any work if pPage is neither overfull nor ** underfull. */ assert( sqlite3pager_iswriteable(pPage->aData) ); pBt = pPage->pBt; if( !pPage->isOverfull && pPage->nFree<pBt->pageSize/2 && pPage->nCell>=2){ relinkCellList(pPage); return SQLITE_OK; } /* ** 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; | > < | | | 2625 2626 2627 2628 2629 2630 2631 2632 2633 2634 2635 2636 2637 2638 2639 2640 2641 2642 2643 2644 2645 2646 2647 2648 2649 2650 2651 2652 2653 2654 2655 2656 2657 2658 2659 2660 2661 2662 2663 2664 | int szCell[(MX_CELL+2)*NB]; /* Local size of all cells */ u8 aCopy[NB][MX_PAGE_SIZE+sizeof(MemPage)]; /* Space for apCopy[] */ /* ** Return without doing any work if pPage is neither overfull nor ** underfull. */ assert( pPage->isInit ); assert( sqlite3pager_iswriteable(pPage->aData) ); pBt = pPage->pBt; if( !pPage->isOverfull && pPage->nFree<pBt->pageSize/2 && pPage->nCell>=2){ relinkCellList(pPage); return SQLITE_OK; } /* ** 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); TRACE(("BALANCE: empty table %d\n", pPage->pgno)); }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 tree 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 ** of the database fle), so it might not be able to hold all of the ** information currently contained in the child. If this is the ** case, then do not do the transfer. Leave page 1 empty except ** for the right-pointer to the child page. The child page becomes |
︙ | ︙ | |||
2661 2662 2663 2664 2665 2666 2667 | 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{ | | | > | | 2684 2685 2686 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 | 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->aData, pChild->aData, 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 %d\n", pChild->pgno, pPage->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 %d is low - no changes\n", pPage->pgno)); 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 |
︙ | ︙ | |||
2703 2704 2705 2706 2707 2708 2709 | 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; | > > > | > | 2727 2728 2729 2730 2731 2732 2733 2734 2735 2736 2737 2738 2739 2740 2741 2742 2743 2744 2745 | 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 %d into %d and balance %d\n", pParent->pgno, pPage->pgno, pPage->pgno)); }else{ TRACE(("BALANCE: begin page %d child of %d\n", pPage->pgno, pParent->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 |
︙ | ︙ | |||
2976 2977 2978 2979 2980 2981 2982 | */ for(i=0; i<nNew; i++){ reparentChildPages(apNew[i]); } reparentChildPages(pParent); /* | | > > < > | < | > | 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 3031 3032 3033 3034 3035 3036 3037 3038 3039 3040 3041 3042 3043 | */ for(i=0; i<nNew; i++){ reparentChildPages(apNew[i]); } reparentChildPages(pParent); /* ** Balance the parent page. Note that the current page (pPage) might ** have been added to the freelist is it might no longer be initialized. ** But the parent page will always be initialized. */ assert( pParent->isInit ); /* assert( pPage->isInit ); // No! pPage might have been added to freelist */ /* pageIntegrity(pPage); // No! pPage might have been added to freelist */ 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: old=%d new=%d cells=%d\n", pPage->pgno, nOld, nNew, nCell)); 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 |
︙ | ︙ | |||
3072 3073 3074 3075 3076 3077 3078 3079 3080 3081 3082 3083 3084 3085 3086 3087 3088 3089 3090 3091 | } if( checkReadLocks(pCur) ){ return SQLITE_LOCKED; /* The table pCur points to has a read lock */ } rc = sqlite3BtreeMoveto(pCur, pKey, nKey, &loc); if( rc ) return rc; pPage = pCur->pPage; assert( pPage->isInit ); rc = sqlite3pager_write(pPage->aData); if( rc ) return rc; rc = fillInCell(pPage, newCell, pKey, nKey, pData, nData, &szNew); if( rc ) return rc; assert( szNew==cellSize(pPage, newCell) ); if( loc==0 ){ int szOld; assert( pCur->idx>=0 && pCur->idx<pPage->nCell ); oldCell = pPage->aCell[pCur->idx]; if( !pPage->leaf ){ memcpy(&newCell[2], &oldCell[2], 4); } | > > > > | 3102 3103 3104 3105 3106 3107 3108 3109 3110 3111 3112 3113 3114 3115 3116 3117 3118 3119 3120 3121 3122 3123 3124 3125 | } if( checkReadLocks(pCur) ){ return SQLITE_LOCKED; /* The table pCur points to has a read lock */ } rc = sqlite3BtreeMoveto(pCur, pKey, nKey, &loc); if( rc ) return rc; pPage = pCur->pPage; TRACE(("INSERT: table=%d nkey=%lld ndata=%d page=%d %s\n", pCur->pgnoRoot, nKey, nData, pPage->pgno, loc==0 ? "overwrite" : "new entry")); assert( pPage->isInit ); rc = sqlite3pager_write(pPage->aData); if( rc ) return rc; rc = fillInCell(pPage, newCell, pKey, nKey, pData, nData, &szNew); if( rc ) return rc; assert( szNew==cellSize(pPage, newCell) ); assert( szNew<=sizeof(newCell) ); if( loc==0 ){ int szOld; assert( pCur->idx>=0 && pCur->idx<pPage->nCell ); oldCell = pPage->aCell[pCur->idx]; if( !pPage->leaf ){ memcpy(&newCell[2], &oldCell[2], 4); } |
︙ | ︙ | |||
3160 3161 3162 3163 3164 3165 3166 3167 3168 3169 3170 3171 3172 3173 3174 3175 3176 3177 3178 3179 3180 3181 3182 3183 3184 3185 3186 | 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); } moveToRoot(pCur); return rc; } | > > > > | 3194 3195 3196 3197 3198 3199 3200 3201 3202 3203 3204 3205 3206 3207 3208 3209 3210 3211 3212 3213 3214 3215 3216 3217 3218 3219 3220 3221 3222 3223 3224 | 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; TRACE(("DELETE: table=%d delete internal from %d replace from leaf %d\n", pCur->pgnoRoot, pPage->pgno, leafCur.pPage->pgno)); 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{ TRACE(("DELETE: table=%d delete from leaf %d\n", pCur->pgnoRoot, pPage->pgno)); dropCell(pPage, pCur->idx, cellSize(pPage, pCell)); rc = balance(pPage); } moveToRoot(pCur); return rc; } |
︙ | ︙ | |||
3245 3246 3247 3248 3249 3250 3251 | if( !pPage->leaf ){ rc = clearDatabasePage(pBt, get4byte(&pPage->aData[6]), pPage->pParent, 1); if( rc ) return rc; } if( freePageFlag ){ rc = freePage(pPage); }else{ | | | 3283 3284 3285 3286 3287 3288 3289 3290 3291 3292 3293 3294 3295 3296 3297 | if( !pPage->leaf ){ rc = clearDatabasePage(pBt, get4byte(&pPage->aData[6]), pPage->pParent, 1); if( rc ) return rc; } if( freePageFlag ){ rc = freePage(pPage); }else{ zeroPage(pPage, pPage->aData[0] | PTF_LEAF); } releasePage(pPage); return rc; } /* ** Delete all information from a single table in the database. |
︙ | ︙ | |||
3572 3573 3574 3575 3576 3577 3578 3579 3580 3581 3582 | IntegrityCk *pCheck, /* Integrity checking context */ int isFreeList, /* True for a freelist. False for overflow page list */ int iPage, /* Page number for first page in the list */ int N, /* Expected number of pages in the list */ char *zContext /* Context for error messages */ ){ int i; char zMsg[100]; while( N-- > 0 ){ unsigned char *pOvfl; if( iPage<1 ){ | > > | > | 3610 3611 3612 3613 3614 3615 3616 3617 3618 3619 3620 3621 3622 3623 3624 3625 3626 3627 3628 3629 3630 3631 | IntegrityCk *pCheck, /* Integrity checking context */ int isFreeList, /* True for a freelist. False for overflow page list */ int iPage, /* Page number for first page in the list */ int N, /* Expected number of pages in the list */ char *zContext /* Context for error messages */ ){ int i; int expected = N; int iFirst = iPage; char zMsg[100]; while( N-- > 0 ){ unsigned char *pOvfl; if( iPage<1 ){ sprintf(zMsg, "%d of %d pages missing from overflow list starting at %d", N+1, expected, iFirst); checkAppendMsg(pCheck, zContext, zMsg); break; } if( checkRef(pCheck, iPage, zContext) ) break; if( sqlite3pager_get(pCheck->pPager, (Pgno)iPage, (void**)&pOvfl) ){ sprintf(zMsg, "failed to get page %d", iPage); checkAppendMsg(pCheck, zContext, zMsg); |
︙ | ︙ | |||
3663 3664 3665 3666 3667 3668 3669 | /* Check that the page exists */ cur.pBt = pBt = pCheck->pBt; maxLocal = pBt->maxLocal; pageSize = pBt->pageSize; if( iPage==0 ) return 0; if( checkRef(pCheck, iPage, zParentContext) ) return 0; | < | 3704 3705 3706 3707 3708 3709 3710 3711 3712 3713 3714 3715 3716 3717 | /* Check that the page exists */ cur.pBt = pBt = pCheck->pBt; maxLocal = pBt->maxLocal; pageSize = pBt->pageSize; if( iPage==0 ) return 0; if( checkRef(pCheck, iPage, zParentContext) ) return 0; if( (rc = getPage(pBt, (Pgno)iPage, &pPage))!=0 ){ sprintf(zMsg, "unable to get the page. error code=%d", rc); checkAppendMsg(pCheck, zContext, zMsg); return 0; } if( (rc = initPage(pPage, pParent))!=0 ){ sprintf(zMsg, "initPage() returns error code %d", rc); |
︙ | ︙ | |||
3687 3688 3689 3690 3691 3692 3693 3694 3695 3696 3697 3698 3699 3700 | for(i=0; i<pPage->nCell; i++){ u8 *pCell = pPage->aCell[i]; u64 nKey, nData; int sz, nHeader; /* Check payload overflow pages */ parseCellHeader(pPage, pCell, &nData, &nKey, &nHeader); sz = nData; if( !pPage->intKey ) sz += nKey; if( sz>maxLocal ){ int nPage = (sz - maxLocal + pageSize - 5)/(pageSize - 4); checkList(pCheck, 0, get4byte(&pCell[nHeader+maxLocal]),nPage,zContext); } | > | 3727 3728 3729 3730 3731 3732 3733 3734 3735 3736 3737 3738 3739 3740 3741 | for(i=0; i<pPage->nCell; i++){ u8 *pCell = pPage->aCell[i]; u64 nKey, nData; int sz, nHeader; /* Check payload overflow pages */ sprintf(zContext, "On tree page %d cell %d: ", iPage, i); parseCellHeader(pPage, pCell, &nData, &nKey, &nHeader); sz = nData; if( !pPage->intKey ) sz += nKey; if( sz>maxLocal ){ int nPage = (sz - maxLocal + pageSize - 5)/(pageSize - 4); checkList(pCheck, 0, get4byte(&pCell[nHeader+maxLocal]),nPage,zContext); } |
︙ | ︙ |
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.33 2004/05/09 20:40:11 drh Exp $ */ #include "sqliteInt.h" #include "pager.h" #include "btree.h" #include "tcl.h" #include <stdlib.h> #include <string.h> |
︙ | ︙ | |||
1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 | } /* ** Register commands with the TCL interpreter. */ int Sqlitetest3_Init(Tcl_Interp *interp){ static struct { char *zName; Tcl_CmdProc *xProc; } aCmd[] = { { "btree_open", (Tcl_CmdProc*)btree_open }, { "btree_close", (Tcl_CmdProc*)btree_close }, { "btree_begin_transaction", (Tcl_CmdProc*)btree_begin_transaction }, | > | 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 | } /* ** Register commands with the TCL interpreter. */ int Sqlitetest3_Init(Tcl_Interp *interp){ extern int sqlite3_btree_trace; static struct { char *zName; Tcl_CmdProc *xProc; } aCmd[] = { { "btree_open", (Tcl_CmdProc*)btree_open }, { "btree_close", (Tcl_CmdProc*)btree_close }, { "btree_begin_transaction", (Tcl_CmdProc*)btree_begin_transaction }, |
︙ | ︙ | |||
1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 | }; 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; } | > > | 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 | }; 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); Tcl_LinkVar(interp, "btree_trace", (char*)&sqlite3_btree_trace, TCL_LINK_INT); return TCL_OK; } |
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.12 2004/05/09 20:40:11 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl if {[info commands btree_open]!=""} { |
︙ | ︙ | |||
30 31 32 33 34 35 36 | # # An explanation for what all these tables are used for is provided below. # do_test btree2-1.1 { expr srand(1) file delete -force test2.bt file delete -force test2.bt-journal | | | > > > | | | | | | | > | | 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 | # # An explanation for what all these tables are used for is provided below. # do_test btree2-1.1 { expr srand(1) file delete -force test2.bt file delete -force test2.bt-journal set ::b [btree_open test2.bt 2000 0] btree_begin_transaction $::b btree_create_table $::b 0 } {2} do_test btree2-1.2 { btree_create_table $::b 0 } {3} do_test btree2-1.3 { btree_create_table $::b 0 } {4} do_test btree2-1.4 { btree_create_table $::b 0 } {5} do_test btree2-1.5 { btree_create_table $::b 0 } {6} do_test btree2-1.6 { set ::c2 [btree_cursor $::b 2 1] btree_insert $::c2 {one} {1} btree_move_to $::c2 {one} btree_delete $::c2 btree_close_cursor $::c2 btree_commit $::b btree_integrity_check $::b 1 2 3 4 5 6 } {} # This test module works by making lots of pseudo-random changes to a # database while simultaneously maintaining an invariant on that database. # Periodically, the script does a sanity check on the database and verifies # that the invariant is satisfied. # |
︙ | ︙ | |||
121 122 123 124 125 126 127 | return [string range $r 0 [expr {$len-1}]] } # Verify the invariants on the database. Return an empty string on # success or an error message if something is amiss. # proc check_invariants {} { | | | 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 | return [string range $r 0 [expr {$len-1}]] } # Verify the invariants on the database. Return an empty string on # success or an error message if something is amiss. # proc check_invariants {} { set ck [btree_integrity_check $::b 1 2 3 4 5 6] if {$ck!=""} { puts "\n*** SANITY:\n$ck" exit return $ck } btree_move_to $::c3 {} btree_move_to $::c4 {} |
︙ | ︙ | |||
190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 | # from the descriptor table. Each changes begins with a random key. # the entry with that key is put in the foreground table with probability # $I and it is put in background with probability (1.0-$I). It gets # a long key with probability $K and long data with probability $D. # set chngcnt 0 proc random_changes {n I K D} { btree_move_to $::c2 N set N [btree_data $::c2] btree_move_to $::c2 L set L [btree_data $::c2] set LM1 [expr {$L-1}] set total [expr {int($N*$n)}] set format %0${L}d for {set i 0} {$i<$total} {incr i} { set k [expr {int(rand()*$N)+1}] set insert [expr {rand()<=$I}] set longkey [expr {rand()<=$K}] set longdata [expr {rand()<=$D}] | > < < < | 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 | # from the descriptor table. Each changes begins with a random key. # the entry with that key is put in the foreground table with probability # $I and it is put in background with probability (1.0-$I). It gets # a long key with probability $K and long data with probability $D. # set chngcnt 0 proc random_changes {n I K D} { global chngcnt btree_move_to $::c2 N set N [btree_data $::c2] btree_move_to $::c2 L set L [btree_data $::c2] set LM1 [expr {$L-1}] set total [expr {int($N*$n)}] set format %0${L}d for {set i 0} {$i<$total} {incr i} { set k [expr {int(rand()*$N)+1}] set insert [expr {rand()<=$I}] set longkey [expr {rand()<=$K}] set longdata [expr {rand()<=$D}] if {$longkey} { set x [expr {rand()}] set keylen [expr {int($x*$x*$x*$x*3000)+10}] } else { set keylen $L } set key [make_payload $k $L $keylen] |
︙ | ︙ | |||
239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 | if {[string match $basekey* [btree_key $::c4]]} { btree_delete $::c4 } } if {[scan [btree_key $::c4] %d kx]<1} {set kx -1} if {$kx==$k} { btree_delete $::c4 } if {$insert} { btree_insert $::c3 $key $data } else { btree_insert $::c4 $key $data } if {$longkey} { btree_insert $::c5 $basekey $keylen } elseif {[btree_move_to $::c5 $basekey]==0} { btree_delete $::c5 } if {$longdata} { btree_insert $::c6 $basekey $datalen } elseif {[btree_move_to $::c6 $basekey]==0} { btree_delete $::c6 } | > > > > > > > > > > > > > > > > | | | | < < < > > | 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 | if {[string match $basekey* [btree_key $::c4]]} { btree_delete $::c4 } } if {[scan [btree_key $::c4] %d kx]<1} {set kx -1} if {$kx==$k} { btree_delete $::c4 } # For debugging - change the "0" to "1" to integrity check after # every change. if 0 { incr chngcnt puts check----$chngcnt set ck [btree_integrity_check $::b 1 2 3 4 5 6] if {$ck!=""} { puts "\nSANITY CHECK FAILED!\n$ck" exit } } if {$insert} { btree_insert $::c3 $key $data } else { btree_insert $::c4 $key $data } if {$longkey} { btree_insert $::c5 $basekey $keylen } elseif {[btree_move_to $::c5 $basekey]==0} { btree_delete $::c5 } if {$longdata} { btree_insert $::c6 $basekey $datalen } elseif {[btree_move_to $::c6 $basekey]==0} { btree_delete $::c6 } # For debugging - change the "0" to "1" to integrity check after # every change. if 0 { incr chngcnt puts check----$chngcnt set ck [btree_integrity_check $::b 1 2 3 4 5 6] if {$ck!=""} { puts "\nSANITY CHECK FAILED!\n$ck" exit } } } } # Repeat this test sequence on database of various sizes # set testno 2 foreach {N L} { |
︙ | ︙ | |||
323 324 325 326 327 328 329 | btree_close_cursor $::c5 btree_close_cursor $::c6 lindex [btree_pager_stats $::b] 1 } {0} do_test btree2-$testno.7 { btree_close $::b } {} | | | < < > | 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 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 | btree_close_cursor $::c5 btree_close_cursor $::c6 lindex [btree_pager_stats $::b] 1 } {0} do_test btree2-$testno.7 { btree_close $::b } {} # For each database size, run various changes tests. # set num2 1 foreach {n I K D} { 0.5 0.5 0.1 0.1 1.0 0.2 0.1 0.1 1.0 0.8 0.1 0.1 2.0 0.0 0.1 0.1 2.0 1.0 0.1 0.1 2.0 0.0 0.0 0.0 2.0 1.0 0.0 0.0 } { set testid btree2-$testno.8.$num2 set hash [md5file test2.bt] do_test $testid.0 { set ::b [btree_open test2.bt 2000 0] set ::c2 [btree_cursor $::b 2 1] set ::c3 [btree_cursor $::b 3 1] 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 do_test $testid.2 [subst { random_changes $n $I $K $D }] {} do_test $testid.3 { check_invariants } {} do_test $testid.4 { btree_close_cursor $::c2 btree_close_cursor $::c3 btree_close_cursor $::c4 btree_close_cursor $::c5 btree_close_cursor $::c6 btree_rollback $::b md5file test2.bt } $hash btree_begin_transaction $::b set ::c2 [btree_cursor $::b 2 1] set ::c3 [btree_cursor $::b 3 1] set ::c4 [btree_cursor $::b 4 1] set ::c5 [btree_cursor $::b 5 1] set ::c6 [btree_cursor $::b 6 1] #if {$testid=="btree2-3.8.4"} {set btree_trace 1} do_test $testid.5 [subst { random_changes $n $I $K $D }] {} do_test $testid.6 { check_invariants } {} do_test $testid.7 { |
︙ | ︙ | |||
399 400 401 402 403 404 405 | btree_close_cursor $::c4 btree_close_cursor $::c5 btree_close_cursor $::c6 lindex [btree_pager_stats $::b] 1 } {0} do_test $testid.9 { btree_close $::b | | | 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 | btree_close_cursor $::c4 btree_close_cursor $::c5 btree_close_cursor $::c6 lindex [btree_pager_stats $::b] 1 } {0} do_test $testid.9 { btree_close $::b set ::b [btree_open test2.bt 2000 0] set ::c2 [btree_cursor $::b 2 1] set ::c3 [btree_cursor $::b 3 1] set ::c4 [btree_cursor $::b 4 1] set ::c5 [btree_cursor $::b 5 1] set ::c6 [btree_cursor $::b 6 1] check_invariants } {} |
︙ | ︙ | |||
421 422 423 424 425 426 427 | } {0} do_test $testid.11 { btree_close $::b } {} incr num2 } incr testno | | | 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 | } {0} do_test $testid.11 { btree_close $::b } {} incr num2 } incr testno set ::b [btree_open test2.bt 2000 0] } # Testing is complete. Shut everything down. # do_test btree-999.1 { lindex [btree_pager_stats $::b] 1 } {0} |
︙ | ︙ |
Deleted test/btree3.test.
|
| < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < |
Deleted test/btree3rb.test.
|
| < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < |
Changes to test/btree4.test.
︙ | ︙ | |||
11 12 13 14 15 16 17 | # This file implements regression tests for SQLite library. The # focus of this script is btree database backend # # This file focuses on testing the sqliteBtreeNext() and # sqliteBtreePrevious() procedures and making sure they are able # to step through an entire table from either direction. # | | | | > > > | 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | # This file implements regression tests for SQLite library. The # focus of this script is btree database backend # # This file focuses on testing the sqliteBtreeNext() and # sqliteBtreePrevious() procedures and making sure they are able # to step through an entire table from either direction. # # $Id: btree4.test,v 1.2 2004/05/09 20:40:12 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl if {[info commands btree_open]!=""} { # Open a test database. # file delete -force test1.bt file delete -force test1.bt-journal set b1 [btree_open test1.bt 2000 0] btree_begin_transaction $b1 do_test btree4-0.1 { btree_create_table $b1 0 } 2 set data {abcdefghijklmnopqrstuvwxyz0123456789} append data $data append data $data append data $data append data $data |
︙ | ︙ |
Deleted test/btree4rb.test.
|
| < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < |