Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Implement a B+tree option (all data stored on leaves). (CVS 1365) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
b8f70d17f06531269caa0a127efb2d25 |
User & Date: | drh 2004-05-12 19:18:16.000 |
Context
2004-05-12
| ||
21:11 | Fix a problem with B+trees. (CVS 1366) (check-in: 64a75c4cd4 user: drh tags: trunk) | |
19:18 | Implement a B+tree option (all data stored on leaves). (CVS 1365) (check-in: b8f70d17f0 user: drh tags: trunk) | |
15:15 | Btree uses signed integers for the rowid. The intToKey() and keyToInt() macros are now no-ops. (CVS 1364) (check-in: fb3c803014 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.129 2004/05/12 19:18:16 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. |
︙ | ︙ | |||
192 193 194 195 196 197 198 | /* ** Page type flags. An ORed combination of these flags appear as the ** first byte of every BTree page. */ #define PTF_INTKEY 0x01 #define PTF_ZERODATA 0x02 | | | | > > | 192 193 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 221 222 223 224 225 226 227 228 | /* ** Page type flags. An ORed combination of these flags appear as the ** first byte of every BTree page. */ #define PTF_INTKEY 0x01 #define PTF_ZERODATA 0x02 #define PTF_LEAFDATA 0x04 #define PTF_LEAF 0x08 /* ** As each page of the file is loaded into memory, an instance of the following ** structure is appended and initialized to zero. This structure stores ** information about the page that is decoded from the raw file page. ** ** 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 table stores keys only */ u8 leafData; /* True if tables stores data on leaves only */ u8 hasData; /* True if this page stores data */ 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 */ |
︙ | ︙ | |||
341 342 343 344 345 346 347 | ){ int n; if( pPage->leaf ){ n = 2; }else{ n = 6; } | | | | | 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 | ){ int n; if( pPage->leaf ){ n = 2; }else{ n = 6; } if( pPage->hasData ){ n += getVarint(&pCell[n], pnData); }else{ *pnData = 0; } n += getVarint(&pCell[n], (u64*)pnKey); *pnHeader = n; } /* ** Compute the total number of bytes that a Cell needs on the main |
︙ | ︙ | |||
398 399 400 401 402 403 404 | 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) ); | > | > > | 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 | 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->leafData == ((c & PTF_LEAFDATA)!=0) ); assert( pPage->intKey == ((c & (PTF_INTKEY|PTF_LEAFDATA))!=0) ); assert( pPage->hasData == !(pPage->zeroData || (!pPage->leaf && pPage->leafData)) ); } 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 ){ |
︙ | ︙ | |||
685 686 687 688 689 690 691 | } 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]; | | > > | 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 | } 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|PTF_LEAFDATA))!=0; pPage->zeroData = (c & PTF_ZERODATA)!=0; pPage->leafData = (c & PTF_LEAFDATA)!=0; pPage->leaf = (c & PTF_LEAF)!=0; pPage->hasData = !(pPage->zeroData || (!pPage->leaf && pPage->leafData)); 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]); |
︙ | ︙ | |||
759 760 761 762 763 764 765 | 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; | | > > | | 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 | 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|PTF_LEAFDATA))!=0; pPage->zeroData = (flags & PTF_ZERODATA)!=0; pPage->leafData = (flags & PTF_LEAFDATA)!=0; pPage->leaf = (flags & PTF_LEAF)!=0; pPage->hasData = !(pPage->zeroData || (!pPage->leaf && pPage->leafData)); pPage->hdrOffset = hdr; pPage->isOverfull = 0; pPage->needRelink = 0; pPage->idxShift = 0; pPage->isInit = 1; pageIntegrity(pPage); } |
︙ | ︙ | |||
1029 1030 1031 1032 1033 1034 1035 | if( rc ) return rc; memcpy(data, zMagicHeader, sizeof(zMagicHeader)); assert( sizeof(zMagicHeader)==16 ); put2byte(&data[16], SQLITE_PAGE_SIZE); data[18] = 1; data[19] = 1; put2byte(&data[22], (SQLITE_PAGE_SIZE-10)/4-12); | | | 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 | if( rc ) return rc; memcpy(data, zMagicHeader, sizeof(zMagicHeader)); assert( sizeof(zMagicHeader)==16 ); put2byte(&data[16], SQLITE_PAGE_SIZE); data[18] = 1; data[19] = 1; put2byte(&data[22], (SQLITE_PAGE_SIZE-10)/4-12); zeroPage(pP1, PTF_INTKEY|PTF_LEAF ); return SQLITE_OK; } /* ** Attempt to start a new transaction. ** ** A transaction must be started before attempting any changes |
︙ | ︙ | |||
1406 1407 1408 1409 1410 1411 1412 | 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 */ } | | | 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 | 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 */ } if( pPage->hasData ){ while( (0x80&*(cell++))!=0 ){} /* Skip the data size number */ } getVarint(cell, pSize); } return SQLITE_OK; } |
︙ | ︙ | |||
1433 1434 1435 1436 1437 1438 1439 | if( !pCur->isValid ){ return pCur->status ? pCur->status : SQLITE_INTERNAL; } pPage = pCur->pPage; assert( pPage!=0 ); assert( pPage->isInit ); pageIntegrity(pPage); | | | 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 | if( !pCur->isValid ){ return pCur->status ? pCur->status : SQLITE_INTERNAL; } pPage = pCur->pPage; assert( pPage!=0 ); assert( pPage->isInit ); pageIntegrity(pPage); if( !pPage->hasData ){ *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 ){ cell += 4; /* Skip the child pointer */ |
︙ | ︙ | |||
1484 1485 1486 1487 1488 1489 1490 | 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 */ } | | | | | 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 | 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->hasData ){ aPayload += getVarint(aPayload, &nData); }else{ nData = 0; } aPayload += getVarint(aPayload, (u64*)&nKey); if( pPage->intKey ){ nKey = 0; } assert( offset>=0 ); if( skipKey ){ |
︙ | ︙ | |||
1631 1632 1633 1634 1635 1636 1637 | 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 */ } | | | | | 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 | 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->hasData ){ aPayload += getVarint(aPayload, &nData); }else{ nData = 0; } aPayload += getVarint(aPayload, (u64*)&nKey); if( pPage->intKey ){ nKey = 0; } maxLocal = pBt->maxLocal; if( skipKey ){ |
︙ | ︙ | |||
1973 1974 1975 1976 1977 1978 1979 | if( pCellKey==0 ) return SQLITE_NOMEM; rc = sqlite3BtreeKey(pCur, 0, nCellKey, pCellKey); c = pCur->xCompare(pCur->pArg, nCellKey, pCellKey, nKey, pKey); sqliteFree(pCellKey); if( rc ) return rc; } if( c==0 ){ | > > > | | | > | 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 | if( pCellKey==0 ) return SQLITE_NOMEM; rc = sqlite3BtreeKey(pCur, 0, nCellKey, pCellKey); c = pCur->xCompare(pCur->pArg, nCellKey, pCellKey, nKey, pKey); sqliteFree(pCellKey); if( rc ) return rc; } if( c==0 ){ if( pPage->leafData && !pPage->leaf ){ break; }else{ pCur->iMatch = c; if( pRes ) *pRes = 0; return SQLITE_OK; } } if( c<0 ){ lwr = pCur->idx+1; }else{ upr = pCur->idx-1; } } |
︙ | ︙ | |||
2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040 | ** successful then set *pRes=0. If the cursor ** was already pointing to the last entry in the database before ** this routine was called, then set *pRes=1. */ int sqlite3BtreeNext(BtCursor *pCur, int *pRes){ int rc; MemPage *pPage = pCur->pPage; assert( pRes!=0 ); if( pCur->isValid==0 ){ *pRes = 1; return SQLITE_OK; } assert( pPage->isInit ); assert( pCur->idx<pPage->nCell ); | > | 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 | ** successful then set *pRes=0. If the cursor ** was already pointing to the last entry in the database before ** this routine was called, then set *pRes=1. */ int sqlite3BtreeNext(BtCursor *pCur, int *pRes){ int rc; MemPage *pPage = pCur->pPage; assert( pRes!=0 ); if( pCur->isValid==0 ){ *pRes = 1; return SQLITE_OK; } assert( pPage->isInit ); assert( pCur->idx<pPage->nCell ); |
︙ | ︙ | |||
2053 2054 2055 2056 2057 2058 2059 | pCur->isValid = 0; return SQLITE_OK; } moveToParent(pCur); pPage = pCur->pPage; }while( pCur->idx>=pPage->nCell ); *pRes = 0; | > > > > > | | 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085 2086 | pCur->isValid = 0; return SQLITE_OK; } moveToParent(pCur); pPage = pCur->pPage; }while( pCur->idx>=pPage->nCell ); *pRes = 0; if( pPage->leafData ){ rc = sqlite3BtreeNext(pCur, pRes); }else{ rc = SQLITE_OK; } return rc; } *pRes = 0; if( pPage->leaf ){ return SQLITE_OK; } rc = moveToLeftmost(pCur); return rc; |
︙ | ︙ | |||
2096 2097 2098 2099 2100 2101 2102 | *pRes = 1; return SQLITE_OK; } moveToParent(pCur); pPage = pCur->pPage; } pCur->idx--; | > > > | > | 2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 2133 | *pRes = 1; return SQLITE_OK; } moveToParent(pCur); pPage = pCur->pPage; } pCur->idx--; if( pPage->leafData ){ rc = sqlite3BtreePrevious(pCur, pRes); }else{ rc = SQLITE_OK; } } *pRes = 0; return rc; } /* ** The TRACE macro will print high-level status information about the |
︙ | ︙ | |||
2331 2332 2333 2334 2335 2336 2337 | int nHeader; /* Fill in the header. */ nHeader = 2; if( !pPage->leaf ){ nHeader += 4; } | | | | 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 | int nHeader; /* Fill in the header. */ nHeader = 2; if( !pPage->leaf ){ nHeader += 4; } if( pPage->hasData ){ nHeader += putVarint(&pCell[nHeader], nData); } nHeader += putVarint(&pCell[nHeader], *(u64*)&nKey); /* Fill in the payload */ if( !pPage->hasData ){ nData = 0; } nPayload = nData; if( pPage->intKey ){ pSrc = pData; nSrc = nData; nData = 0; |
︙ | ︙ | |||
2683 2684 2685 2686 2687 2688 2689 2690 2691 2692 2693 2694 2695 2696 | int nNew; /* Number of pages in apNew[] */ int nDiv; /* Number of cells in apDiv[] */ int i, j, k; /* Loop counters */ 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 */ | > | 2706 2707 2708 2709 2710 2711 2712 2713 2714 2715 2716 2717 2718 2719 2720 | int nNew; /* Number of pages in apNew[] */ int nDiv; /* Number of cells in apDiv[] */ int i, j, k; /* Loop counters */ 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 leafData; /* True if pPage is a leaf of a LEAFDATA tree */ 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 */ |
︙ | ︙ | |||
2709 2710 2711 2712 2713 2714 2715 | /* ** Return without doing any work if pPage is neither overfull nor ** underfull. */ assert( pPage->isInit ); assert( sqlite3pager_iswriteable(pPage->aData) ); pBt = pPage->pBt; | | | 2733 2734 2735 2736 2737 2738 2739 2740 2741 2742 2743 2744 2745 2746 2747 | /* ** 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/3 && 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. |
︙ | ︙ | |||
2908 2909 2910 2911 2912 2913 2914 2915 2916 2917 2918 2919 2920 2921 2922 | ** into aTemp[]. In this wall, all cells in apCell[] are without ** child pointers. If siblings are not leaves, then all cell in ** apCell[] include child pointers. Either way, all cells in apCell[] ** are alike. */ nCell = 0; leafCorrection = pPage->leaf*4; for(i=0; i<nOld; i++){ 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 ){ | > > > > > | | | | | | | | | | | | | | | > > | 2932 2933 2934 2935 2936 2937 2938 2939 2940 2941 2942 2943 2944 2945 2946 2947 2948 2949 2950 2951 2952 2953 2954 2955 2956 2957 2958 2959 2960 2961 2962 2963 2964 2965 2966 2967 2968 2969 2970 2971 2972 2973 2974 2975 2976 2977 2978 2979 2980 2981 2982 2983 2984 2985 2986 2987 2988 2989 2990 2991 2992 2993 2994 | ** into aTemp[]. In this wall, all cells in apCell[] are without ** child pointers. If siblings are not leaves, then all cell in ** apCell[] include child pointers. Either way, all cells in apCell[] ** are alike. */ nCell = 0; leafCorrection = pPage->leaf*4; leafData = pPage->leafData && pPage->leaf; for(i=0; i<nOld; i++){ 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 ){ if( leafData ){ int sz = cellSize(pParent, apDiv[i]); dropCell(pParent, nxDiv, sz); }else{ 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 ); } nCell++; } } } /* ** Figure out the number of pages needed to hold all nCell cells. ** Store this number in "k". Also compute szNew[] which is the total ** size of all cells on the i-th page and cntNew[] which is the index ** in apCell[] of the cell that divides page i from page i+1. ** cntNew[k] should equal nCell. ** ** This little patch of code is critical for keeping the tree ** balanced. */ usableSpace = pBt->pageSize - 10 + leafCorrection; for(subtotal=k=i=0; i<nCell; i++){ subtotal += szCell[i]; if( subtotal > usableSpace ){ szNew[k] = subtotal - szCell[i]; cntNew[k] = i; if( leafData ){ i--; } subtotal = 0; k++; } } szNew[k] = subtotal; cntNew[k] = nCell; k++; |
︙ | ︙ | |||
3060 3061 3062 3063 3064 3065 3066 | insertCell(pNew, pNew->nCell, apCell[j], szCell[j], 0); j++; } assert( pNew->nCell>0 ); assert( !pNew->isOverfull ); relinkCellList(pNew); if( i<nNew-1 && j<nCell ){ | | > > > > > > > > > > > > | | 3091 3092 3093 3094 3095 3096 3097 3098 3099 3100 3101 3102 3103 3104 3105 3106 3107 3108 3109 3110 3111 3112 3113 3114 3115 3116 3117 3118 3119 3120 3121 3122 3123 3124 3125 3126 | insertCell(pNew, pNew->nCell, apCell[j], szCell[j], 0); j++; } assert( pNew->nCell>0 ); assert( !pNew->isOverfull ); relinkCellList(pNew); if( i<nNew-1 && j<nCell ){ u8 *pCell; u8 *pTemp; int sz; pCell = apCell[j]; sz = szCell[j] + leafCorrection; if( !pNew->leaf ){ memcpy(&pNew->aData[6], pCell+2, 4); pTemp = 0; }else if( leafData ){ i64 nKey; u64 nData; int nHeader; j--; parseCellHeader(pNew, apCell[j], &nData, &nKey, &nHeader); pCell = aInsBuf[i]; fillInCell(pParent, pCell, 0, nKey, 0, 0, &sz); pTemp = 0; }else{ pCell -= 4; pTemp = aInsBuf[i]; } insertCell(pParent, nxDiv, pCell, sz, pTemp); put4byte(&pParent->aCell[nxDiv][2], pNew->pgno); j++; nxDiv++; } } assert( j==nCell ); if( (pageFlags & PTF_LEAF)==0 ){ |
︙ | ︙ | |||
3196 3197 3198 3199 3200 3201 3202 3203 3204 3205 3206 3207 3208 3209 | 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->intKey || nKey>=0 ); 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); | > | 3239 3240 3241 3242 3243 3244 3245 3246 3247 3248 3249 3250 3251 3252 3253 | 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->intKey || nKey>=0 ); assert( pPage->leaf || !pPage->leafData ); 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); |
︙ | ︙ | |||
3280 3281 3282 3283 3284 3285 3286 3287 3288 3289 3290 3291 3292 3293 | ** to be a leaf so we can use it. */ BtCursor leafCur; unsigned char *pNext; int szNext; int notUsed; unsigned char tempCell[MX_CELL_SIZE]; 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); | > | 3324 3325 3326 3327 3328 3329 3330 3331 3332 3333 3334 3335 3336 3337 3338 | ** to be a leaf so we can use it. */ BtCursor leafCur; unsigned char *pNext; int szNext; int notUsed; unsigned char tempCell[MX_CELL_SIZE]; assert( !pPage->leafData ); 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); |
︙ | ︙ | |||
3514 3515 3516 3517 3518 3519 3520 | rc = getPage(pBt, (Pgno)pgno, &pPage); if( rc ){ return rc; } hdr = pPage->hdrOffset; data = pPage->aData; c = data[hdr]; | | > > | 3559 3560 3561 3562 3563 3564 3565 3566 3567 3568 3569 3570 3571 3572 3573 3574 3575 3576 3577 | rc = getPage(pBt, (Pgno)pgno, &pPage); if( rc ){ return rc; } hdr = pPage->hdrOffset; data = pPage->aData; c = data[hdr]; pPage->intKey = (c & (PTF_INTKEY|PTF_LEAFDATA))!=0; pPage->zeroData = (c & PTF_ZERODATA)!=0; pPage->leafData = (c & PTF_LEAFDATA)!=0; pPage->leaf = (c & PTF_LEAF)!=0; pPage->hasData = !(pPage->zeroData || (!pPage->leaf && pPage->leafData)); 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 ){ |
︙ | ︙ |
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.47 2004/05/12 19:18:17 drh Exp $ */ #ifndef _BTREE_H_ #define _BTREE_H_ /* TODO: This definition is just included so other modules compile. It ** needs to be revisited. */ |
︙ | ︙ | |||
51 52 53 54 55 56 57 | const char *sqlite3BtreeGetFilename(Btree *); int sqlite3BtreeCopyFile(Btree *, Btree *); /* The flags parameter to sqlite3BtreeCreateTable can be the bitwise OR ** of the following flags: */ | | | > | 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 | const char *sqlite3BtreeGetFilename(Btree *); int sqlite3BtreeCopyFile(Btree *, Btree *); /* The flags parameter to sqlite3BtreeCreateTable can be the bitwise OR ** of the following flags: */ #define BTREE_INTKEY 1 /* Table has only 64-bit signed integer keys */ #define BTREE_ZERODATA 2 /* Table has keys only - no data */ #define BTREE_LEAFDATA 4 /* Data stored in leaves only. Implies INTKEY */ int sqlite3BtreeDropTable(Btree*, int); int sqlite3BtreeClearTable(Btree*, int); int sqlite3BtreeGetMeta(Btree*, int idx, u32 *pValue); int sqlite3BtreeUpdateMeta(Btree*, int idx, u32 value); int sqlite3BtreeCursor( |
︙ | ︙ |
Changes to test/btree5.test.
1 2 3 4 5 6 7 8 9 10 11 12 13 | # 2004 May 10 # # 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 | # 2004 May 10 # # 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: btree5.test,v 1.3 2004/05/12 19:18:17 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl # Attempting to read table 1 of an empty file gives an SQLITE_EMPTY # error. |
︙ | ︙ | |||
119 120 121 122 123 124 125 | if {[set data [btree_data $c1]] ne "data-for-[btree_key $c1]"} { return "wrong data for entry $cnt" } set n [string length $data] set fdata1 [btree_fetch_data $c1 $n] set fdata2 [btree_fetch_data $c1 -1] if {$fdata1 ne "" && $fdata1 ne $data} { | < | 119 120 121 122 123 124 125 126 127 128 129 130 131 132 | if {[set data [btree_data $c1]] ne "data-for-[btree_key $c1]"} { return "wrong data for entry $cnt" } set n [string length $data] set fdata1 [btree_fetch_data $c1 $n] set fdata2 [btree_fetch_data $c1 -1] if {$fdata1 ne "" && $fdata1 ne $data} { return "DataFetch returned the wrong value with amt=$n" } if {$fdata1 ne $fdata2} { return "DataFetch returned the wrong value when amt=-1" } if {$n>10} { set fdata3 [btree_fetch_data $c1 10] |
︙ | ︙ | |||
150 151 152 153 154 155 156 | set c1 [btree_cursor $b1 1 1] set btree_trace 0 # Do the tests. # set cnt 0 for {set i 1} {$i<=100} {incr i} { | | | | | | 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 | set c1 [btree_cursor $b1 1 1] set btree_trace 0 # Do the tests. # set cnt 0 for {set i 1} {$i<=100} {incr i} { do_test btree5-2.$i.1 { random_inserts 200 incr cnt 200 check_table $cnt } {} do_test btree5-2.$i.2 { btree_integrity_check $b1 1 } {} do_test btree5-2.$i.3 { random_deletes 190 incr cnt -190 check_table $cnt } {} do_test btree5-2.$i.4 { btree_integrity_check $b1 1 } {} } btree_close_cursor $c1 btree_commit $b1 btree_begin_transaction $b1 |
︙ | ︙ |
Added test/btree6.test.
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1 2 3 4 5 6 7 8 9 10 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 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 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 | # 2004 May 10 # # 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 - specifically # the B+tree tables. B+trees store all data on the leaves rather # that storing data with keys on interior nodes. # # $Id: btree6.test,v 1.1 2004/05/12 19:18:17 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl # Insert many entries into the table that cursor $cur points to. # The table should be an INTKEY table. # # Stagger the inserts. After the inserts complete, go back and do # deletes. Stagger the deletes too. Repeat this several times. # # Do N inserts into table $tab using random keys between 0 and 1000000 # proc random_inserts {cur N} { global inscnt while {$N>0} { set k [expr {int(rand()*1000000)}] if {[btree_move_to $cur $k]==0} { continue; # entry already exists } incr inscnt btree_insert $cur $k data-for-$k incr N -1 } } set inscnt 0 # Do N delete from the table that $cur points to. # proc random_deletes {cur N} { while {$N>0} { set k [expr {int(rand()*1000000)}] btree_move_to $cur $k btree_delete $cur incr N -1 } } # Make sure the table that $cur points to has exactly N entries. # Make sure the data for each entry agrees with its key. # proc check_table {cur N} { btree_first $cur set cnt 0 while {![btree_eof $cur]} { if {[set data [btree_data $cur]] ne "data-for-[btree_key $cur]"} { return "wrong data for entry $cnt" } set n [string length $data] set fdata1 [btree_fetch_data $cur $n] set fdata2 [btree_fetch_data $cur -1] if {$fdata1 ne "" && $fdata1 ne $data} { return "DataFetch returned the wrong value with amt=$n" } if {$fdata1 ne $fdata2} { return "DataFetch returned the wrong value when amt=-1" } if {$n>10} { set fdata3 [btree_fetch_data $cur 10] if {$fdata3 ne [string range $data 0 9]} { return "DataFetch returned the wrong value when amt=10" } } incr cnt btree_next $cur } if {$cnt!=$N} { return "wrong number of entries. Got $cnt. Looking for $N" } return {} } # Initialize the database # file delete -force test1.bt file delete -force test1.bt-journal set b1 [btree_open test1.bt 2000 0] btree_begin_transaction $b1 set tab [btree_create_table $b1 5] set cur [btree_cursor $b1 $tab 1] set btree_trace 0 expr srand(1) # Do the tests. # set cnt 0 for {set i 1} {$i<=100} {incr i} { do_test btree6-1.$i.1 { random_inserts $cur 200 incr cnt 200 check_table $cur $cnt } {} do_test btree6-1.$i.2 { btree_integrity_check $b1 1 $tab } {} do_test btree6-1.$i.3 { random_deletes $cur 190 incr cnt -190 check_table $cur $cnt } {} do_test btree6-1.$i.4 { btree_integrity_check $b1 1 $tab } {} } btree_close_cursor $cur btree_commit $b1 finish_test |