Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Btree uses signed integers for the rowid. The intToKey() and keyToInt() macros are now no-ops. (CVS 1364) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
fb3c80301441f0d255164578601439db |
User & Date: | drh 2004-05-12 15:15:47.000 |
Context
2004-05-12
| ||
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) | |
13:30 | The pager now handles file ":memory:" complete in memory with no disk I/O. (CVS 1363) (check-in: 97de9f7cee 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.128 2004/05/12 15:15:47 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. |
︙ | ︙ | |||
332 333 334 335 336 337 338 | /* ** Parse a cell header and fill in the CellInfo structure. */ static void parseCellHeader( MemPage *pPage, /* Page containing the cell */ unsigned char *pCell, /* The cell */ u64 *pnData, /* Number of bytes of data in payload */ | | | | > | 332 333 334 335 336 337 338 339 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 | /* ** Parse a cell header and fill in the CellInfo structure. */ static void parseCellHeader( MemPage *pPage, /* Page containing the cell */ unsigned char *pCell, /* The cell */ u64 *pnData, /* Number of bytes of data in payload */ i64 *pnKey, /* Number of bytes of key, or key value for intKey */ int *pnHeader /* Size of header in bytes. Offset to payload */ ){ int n; if( pPage->leaf ){ n = 2; }else{ n = 6; } if( pPage->zeroData ){ *pnData = 0; }else{ n += getVarint(&pCell[n], pnData); } n += getVarint(&pCell[n], (u64*)pnKey); *pnHeader = n; } /* ** Compute the total number of bytes that a Cell needs on the main ** database page. The number returned includes the Cell header, ** local payload storage, and the pointer to overflow pages (if ** applicable). Additional space allocated on overflow pages ** is NOT included in the value returned from this routine. */ static int cellSize(MemPage *pPage, unsigned char *pCell){ int n; u64 nData; i64 nKey; int nPayload, maxPayload; parseCellHeader(pPage, pCell, &nData, &nKey, &n); nPayload = (int)nData; if( !pPage->intKey ){ nPayload += (int)nKey; } |
︙ | ︙ | |||
863 864 865 866 867 868 869 870 871 872 873 874 875 876 | int rc; /* ** The following asserts make sure that structures used by the btree are ** the right size. This is to guard against size changes that result ** when compiling on a different architecture. */ assert( sizeof(u64)==8 ); assert( sizeof(u32)==4 ); assert( sizeof(u16)==2 ); assert( sizeof(Pgno)==4 ); assert( sizeof(ptr)==sizeof(char*) ); assert( sizeof(uptr)==sizeof(ptr) ); | > | 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 | int rc; /* ** The following asserts make sure that structures used by the btree are ** the right size. This is to guard against size changes that result ** when compiling on a different architecture. */ assert( sizeof(i64)==8 ); assert( sizeof(u64)==8 ); assert( sizeof(u32)==4 ); assert( sizeof(u16)==2 ); assert( sizeof(Pgno)==4 ); assert( sizeof(ptr)==sizeof(char*) ); assert( sizeof(uptr)==sizeof(ptr) ); |
︙ | ︙ | |||
1388 1389 1390 1391 1392 1393 1394 | ** Set *pSize to the size of the buffer needed to hold the value of ** the key for the current entry. If the cursor is not pointing ** to a valid entry, *pSize is set to 0. ** ** For a table with the INTKEY flag set, this routine returns the key ** itself, not the number of bytes in the key. */ | | | 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 | ** Set *pSize to the size of the buffer needed to hold the value of ** the key for the current entry. If the cursor is not pointing ** to a valid entry, *pSize is set to 0. ** ** For a table with the INTKEY flag set, this routine returns the key ** itself, not the number of bytes in the key. */ int sqlite3BtreeKeySize(BtCursor *pCur, i64 *pSize){ MemPage *pPage; unsigned char *cell; if( !pCur->isValid ){ *pSize = 0; }else{ pPage = pCur->pPage; |
︙ | ︙ | |||
1467 1468 1469 1470 1471 1472 1473 | int skipKey /* offset begins at data if this is true */ ){ unsigned char *aPayload; Pgno nextPage; int rc; MemPage *pPage; Btree *pBt; | | > | | 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 | int skipKey /* offset begins at data if this is true */ ){ unsigned char *aPayload; Pgno nextPage; int rc; MemPage *pPage; Btree *pBt; u64 nData; i64 nKey; int maxLocal, ovflSize; assert( pCur!=0 && pCur->pPage!=0 ); assert( pCur->isValid ); pBt = pCur->pBt; pPage = pCur->pPage; pageIntegrity(pPage); assert( pCur->idx>=0 && pCur->idx<pPage->nCell ); aPayload = pPage->aCell[pCur->idx]; aPayload += 2; /* Skip the next cell index */ if( !pPage->leaf ){ aPayload += 4; /* Skip the child pointer */ } if( pPage->zeroData ){ nData = 0; }else{ aPayload += getVarint(aPayload, &nData); } aPayload += getVarint(aPayload, (u64*)&nKey); if( pPage->intKey ){ nKey = 0; } assert( offset>=0 ); if( skipKey ){ offset += nKey; } |
︙ | ︙ | |||
1613 1614 1615 1616 1617 1618 1619 | BtCursor *pCur, /* Cursor pointing to entry to read from */ int amt, /* Amount requested */ int skipKey /* read beginning at data if this is true */ ){ unsigned char *aPayload; MemPage *pPage; Btree *pBt; | | > | | 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 | BtCursor *pCur, /* Cursor pointing to entry to read from */ int amt, /* Amount requested */ int skipKey /* read beginning at data if this is true */ ){ unsigned char *aPayload; MemPage *pPage; Btree *pBt; u64 nData; i64 nKey; int maxLocal; assert( pCur!=0 && pCur->pPage!=0 ); assert( pCur->isValid ); pBt = pCur->pBt; pPage = pCur->pPage; pageIntegrity(pPage); assert( pCur->idx>=0 && pCur->idx<pPage->nCell ); aPayload = pPage->aCell[pCur->idx]; aPayload += 2; /* Skip the next cell index */ if( !pPage->leaf ){ aPayload += 4; /* Skip the child pointer */ } if( pPage->zeroData ){ nData = 0; }else{ aPayload += getVarint(aPayload, &nData); } aPayload += getVarint(aPayload, (u64*)&nKey); if( pPage->intKey ){ nKey = 0; } maxLocal = pBt->maxLocal; if( skipKey ){ aPayload += nKey; maxLocal -= nKey; |
︙ | ︙ | |||
1922 1923 1924 1925 1926 1927 1928 | ** ** *pRes==0 The cursor is left pointing at an entry that ** exactly matches pKey. ** ** *pRes>0 The cursor is left pointing at an entry that ** is larger than pKey. */ | | | 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 | ** ** *pRes==0 The cursor is left pointing at an entry that ** exactly matches pKey. ** ** *pRes>0 The cursor is left pointing at an entry that ** is larger than pKey. */ int sqlite3BtreeMoveto(BtCursor *pCur, const void *pKey, i64 nKey, int *pRes){ int rc; if( pCur->status ){ return pCur->status; } rc = moveToRoot(pCur); if( rc ) return rc; |
︙ | ︙ | |||
1947 1948 1949 1950 1951 1952 1953 | MemPage *pPage = pCur->pPage; int c = -1; /* pRes return if table is empty must be -1 */ lwr = 0; upr = pPage->nCell-1; pageIntegrity(pPage); while( lwr<=upr ){ const void *pCellKey; | | | 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 | MemPage *pPage = pCur->pPage; int c = -1; /* pRes return if table is empty must be -1 */ lwr = 0; upr = pPage->nCell-1; pageIntegrity(pPage); while( lwr<=upr ){ const void *pCellKey; i64 nCellKey; pCur->idx = (lwr+upr)/2; sqlite3BtreeKeySize(pCur, &nCellKey); if( pPage->intKey ){ if( nCellKey<nKey ){ c = -1; }else if( nCellKey>nKey ){ c = +1; |
︙ | ︙ | |||
2265 2266 2267 2268 2269 2270 2271 | /* ** Free any overflow pages associated with the given Cell. */ static int clearCell(MemPage *pPage, unsigned char *pCell){ Btree *pBt = pPage->pBt; int rc, n, nPayload; | | > | 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 | /* ** Free any overflow pages associated with the given Cell. */ static int clearCell(MemPage *pPage, unsigned char *pCell){ Btree *pBt = pPage->pBt; int rc, n, nPayload; u64 nData; i64 nKey; Pgno ovflPgno; parseCellHeader(pPage, pCell, &nData, &nKey, &n); assert( (nData&0x000000007fffffff)==nData ); nPayload = (int)nData; if( !pPage->intKey ){ nPayload += nKey; |
︙ | ︙ | |||
2305 2306 2307 2308 2309 2310 2311 | ** area. pCell might point to some temporary storage. The cell will ** be constructed in this temporary area then copied into pPage->aData ** later. */ static int fillInCell( MemPage *pPage, /* The page that contains the cell */ unsigned char *pCell, /* Complete text of the cell */ | | | 2310 2311 2312 2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 | ** area. pCell might point to some temporary storage. The cell will ** be constructed in this temporary area then copied into pPage->aData ** later. */ static int fillInCell( MemPage *pPage, /* The page that contains the cell */ unsigned char *pCell, /* Complete text of the cell */ const void *pKey, i64 nKey, /* The key */ const void *pData,int nData, /* The data */ int *pnSize /* Write cell size here */ ){ int nPayload; const void *pSrc; int nSrc, n, rc; int spaceLeft; |
︙ | ︙ | |||
2329 2330 2331 2332 2333 2334 2335 | nHeader = 2; if( !pPage->leaf ){ nHeader += 4; } if( !pPage->zeroData ){ nHeader += putVarint(&pCell[nHeader], nData); } | | | 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 | nHeader = 2; if( !pPage->leaf ){ nHeader += 4; } if( !pPage->zeroData ){ nHeader += putVarint(&pCell[nHeader], nData); } nHeader += putVarint(&pCell[nHeader], *(u64*)&nKey); /* Fill in the payload */ if( pPage->zeroData ){ nData = 0; } nPayload = nData; if( pPage->intKey ){ |
︙ | ︙ | |||
3162 3163 3164 3165 3166 3167 3168 | ** is left pointing at a random location. ** ** For an INTKEY table, only the nKey value of the key is used. pKey is ** ignored. For a ZERODATA table, the pData and nData are both ignored. */ int sqlite3BtreeInsert( BtCursor *pCur, /* Insert data into the table of this cursor */ | | | 3167 3168 3169 3170 3171 3172 3173 3174 3175 3176 3177 3178 3179 3180 3181 | ** is left pointing at a random location. ** ** For an INTKEY table, only the nKey value of the key is used. pKey is ** ignored. For a ZERODATA table, the pData and nData are both ignored. */ int sqlite3BtreeInsert( BtCursor *pCur, /* Insert data into the table of this cursor */ const void *pKey, i64 nKey, /* The key of the new record */ const void *pData, int nData /* The data of the new record */ ){ int rc; int loc; int szNew; MemPage *pPage; Btree *pBt = pCur->pBt; |
︙ | ︙ | |||
3190 3191 3192 3193 3194 3195 3196 3197 3198 3199 3200 3201 3202 3203 | } 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); | > | 3195 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); |
︙ | ︙ | |||
3518 3519 3520 3521 3522 3523 3524 | 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 ){ | | > | 3524 3525 3526 3527 3528 3529 3530 3531 3532 3533 3534 3535 3536 3537 3538 3539 | printf("PAGE %d: flags=0x%02x frag=%d parent=%d\n", pgno, data[hdr], data[hdr+5], (pPage->isInit && pPage->pParent) ? pPage->pParent->pgno : 0); i = 0; assert( hdr == (pgno==1 ? 100 : 0) ); idx = get2byte(&data[hdr+3]); while( idx>0 && idx<=pBt->pageSize ){ u64 nData; i64 nKey; int nHeader; Pgno child; unsigned char *pCell = &data[idx]; int sz = cellSize(pPage, pCell); sprintf(range,"%d..%d", idx, idx+sz-1); parseCellHeader(pPage, pCell, &nData, &nKey, &nHeader); if( pPage->leaf ){ |
︙ | ︙ | |||
3814 3815 3816 3817 3818 3819 3820 | /* Check out all the cells. */ depth = 0; cur.pPage = pPage; for(i=0; i<pPage->nCell; i++){ u8 *pCell = pPage->aCell[i]; | | > | 3821 3822 3823 3824 3825 3826 3827 3828 3829 3830 3831 3832 3833 3834 3835 3836 | /* Check out all the cells. */ depth = 0; cur.pPage = pPage; for(i=0; i<pPage->nCell; i++){ u8 *pCell = pPage->aCell[i]; i64 nKey; u64 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; |
︙ | ︙ |
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.46 2004/05/12 15:15:47 drh Exp $ */ #ifndef _BTREE_H_ #define _BTREE_H_ /* TODO: This definition is just included so other modules compile. It ** needs to be revisited. */ |
︙ | ︙ | |||
69 70 71 72 73 74 75 | int wrFlag, /* 1 for writing. 0 for read-only */ int(*)(void*,int,const void*,int,const void*), /* Key comparison function */ void*, /* First argument to compare function */ BtCursor **ppCursor /* Returned cursor */ ); int sqlite3BtreeCloseCursor(BtCursor*); | | | | | 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 | int wrFlag, /* 1 for writing. 0 for read-only */ int(*)(void*,int,const void*,int,const void*), /* Key comparison function */ void*, /* First argument to compare function */ BtCursor **ppCursor /* Returned cursor */ ); int sqlite3BtreeCloseCursor(BtCursor*); int sqlite3BtreeMoveto(BtCursor*, const void *pKey, i64 nKey, int *pRes); int sqlite3BtreeDelete(BtCursor*); int sqlite3BtreeInsert(BtCursor*, const void *pKey, i64 nKey, const void *pData, int nData); int sqlite3BtreeFirst(BtCursor*, int *pRes); int sqlite3BtreeLast(BtCursor*, int *pRes); int sqlite3BtreeNext(BtCursor*, int *pRes); int sqlite3BtreeEof(BtCursor*); int sqlite3BtreeFlags(BtCursor*); int sqlite3BtreePrevious(BtCursor*, int *pRes); int sqlite3BtreeKeySize(BtCursor*, i64 *pSize); int sqlite3BtreeKey(BtCursor*, u32 offset, u32 amt, void*); const void *sqlite3BtreeKeyFetch(BtCursor*, int amt); const void *sqlite3BtreeDataFetch(BtCursor*, int amt); int sqlite3BtreeDataSize(BtCursor*, u32 *pSize); int sqlite3BtreeData(BtCursor*, u32 offset, u32 amt, void*); char *sqlite3BtreeIntegrityCheck(Btree*, int *aRoot, int nRoot); |
︙ | ︙ |
Changes to src/vdbeInt.h.
︙ | ︙ | |||
13 14 15 16 17 18 19 | ** VDBE. This information used to all be at the top of the single ** source code file "vdbe.c". When that file became too big (over ** 6000 lines long) it was split up into several smaller files and ** this header information was factored out. */ /* | | | < | | | 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | ** VDBE. This information used to all be at the top of the single ** source code file "vdbe.c". When that file became too big (over ** 6000 lines long) it was split up into several smaller files and ** this header information was factored out. */ /* ** intToKey() and keyToInt() used to transform the rowid. But with ** the latest versions of the design they are no-ops. */ #define keyToInt(X) (X) #define intToKey(X) (X) /* ** The makefile scans this source file and creates the following ** array of string constants which are the names of all VDBE opcodes. ** This array is defined in a separate source code file named opcode.c ** which is automatically generated by the makefile. */ |
︙ | ︙ |