Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Remove some unnecessary code and complication from the btree interface. (CVS 909) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
35cc7c7d37d9ca486e7f300efe80a78a |
User & Date: | drh 2003-04-16 01:28:16.000 |
Context
2003-04-16
| ||
02:17 | Simplify the number processing code. Fix for ticket #281. (CVS 910) (check-in: 4326b52a39 user: drh tags: trunk) | |
01:28 | Remove some unnecessary code and complication from the btree interface. (CVS 909) (check-in: 35cc7c7d37 user: drh tags: trunk) | |
2003-04-15
| ||
19:22 | Get triggers working on tables with INTEGER PRIMARY KEYs. Ticket #291. This may also fix #159. Still need to add tests so both bugs remain open for the time being. (CVS 908) (check-in: 0b996959b8 user: drh tags: trunk) | |
Changes
Changes to src/btree.c.
1 2 3 4 5 6 7 8 9 10 11 | /* ** 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. ** ************************************************************************* | | | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | /* ** 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. ** ************************************************************************* ** $Id: btree.c,v 1.89 2003/04/16 01:28: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. |
︙ | ︙ | |||
45 46 47 48 49 50 51 | ** ** The first page of the file contains a magic string used to verify that ** the file really is a valid BTree database, a pointer to a list of unused ** pages in the file, and some meta information. The root of the first ** BTree begins on page 2 of the file. (Pages are numbered beginning with ** 1, not 0.) Thus a minimum database contains 2 pages. */ | < < < < < < < | 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | ** ** The first page of the file contains a magic string used to verify that ** the file really is a valid BTree database, a pointer to a list of unused ** pages in the file, and some meta information. The root of the first ** BTree begins on page 2 of the file. (Pages are numbered beginning with ** 1, not 0.) Thus a minimum database contains 2 pages. */ #include "sqliteInt.h" #include "pager.h" #include "btree.h" #include <assert.h> /* Forward declarations */ static BtOps sqliteBtreeOps; |
︙ | ︙ | |||
385 386 387 388 389 390 391 | */ #define SKIP_NONE 0 /* Always step the cursor */ #define SKIP_NEXT 1 /* The next sqliteBtreeNext() is a no-op */ #define SKIP_PREV 2 /* The next sqliteBtreePrevious() is a no-op */ #define SKIP_INVALID 3 /* Calls to Next() and Previous() are invalid */ /* Forward declarations */ | | | 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 | */ #define SKIP_NONE 0 /* Always step the cursor */ #define SKIP_NEXT 1 /* The next sqliteBtreeNext() is a no-op */ #define SKIP_PREV 2 /* The next sqliteBtreePrevious() is a no-op */ #define SKIP_INVALID 3 /* Calls to Next() and Previous() are invalid */ /* Forward declarations */ static int fileBtreeCloseCursor(BtCursor *pCur); /* ** Routines for byte swapping. */ u16 swab16(u16 x){ return ((x & 0xff)<<8) | ((x>>8)&0xff); } |
︙ | ︙ | |||
729 730 731 732 733 734 735 | *ppBtree = pBt; return SQLITE_OK; } /* ** Close an open database and invalidate all cursors. */ | | | | 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 | *ppBtree = pBt; return SQLITE_OK; } /* ** Close an open database and invalidate all cursors. */ static int fileBtreeClose(Btree *pBt){ while( pBt->pCursor ){ fileBtreeCloseCursor(pBt->pCursor); } sqlitepager_close(pBt->pPager); sqliteFree(pBt); return SQLITE_OK; } /* |
︙ | ︙ | |||
753 754 755 756 757 758 759 | ** and the database cannot be corrupted if this program ** crashes. But if the operating system crashes or there is ** an abrupt power failure when synchronous is off, the database ** could be left in an inconsistent and unrecoverable state. ** Synchronous is on by default so database corruption is not ** normally a worry. */ | | | | 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 | ** and the database cannot be corrupted if this program ** crashes. But if the operating system crashes or there is ** an abrupt power failure when synchronous is off, the database ** could be left in an inconsistent and unrecoverable state. ** Synchronous is on by default so database corruption is not ** normally a worry. */ static int fileBtreeSetCacheSize(Btree *pBt, int mxPage){ sqlitepager_set_cachesize(pBt->pPager, mxPage); return SQLITE_OK; } /* ** Change the way data is synced to disk in order to increase or decrease ** how well the database resists damage due to OS crashes and power ** failures. Level 1 is the same as asynchronous (no syncs() occur and ** there is a high probability of damage) Level 2 is the default. There ** is a very low but non-zero probability of damage. Level 3 reduces the ** probability of damage to near zero but with a write performance reduction. */ static int fileBtreeSetSafetyLevel(Btree *pBt, int level){ sqlitepager_set_safety_level(pBt->pPager, level); return SQLITE_OK; } /* ** Get a reference to page1 of the database file. This will ** also acquire a readlock on that file. |
︙ | ︙ | |||
873 874 875 876 877 878 879 | ** sqliteBtreeCreateIndex() ** sqliteBtreeClearTable() ** sqliteBtreeDropTable() ** sqliteBtreeInsert() ** sqliteBtreeDelete() ** sqliteBtreeUpdateMeta() */ | | | 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 | ** sqliteBtreeCreateIndex() ** sqliteBtreeClearTable() ** sqliteBtreeDropTable() ** sqliteBtreeInsert() ** sqliteBtreeDelete() ** sqliteBtreeUpdateMeta() */ static int fileBtreeBeginTrans(Btree *pBt){ int rc; if( pBt->inTrans ) return SQLITE_ERROR; if( pBt->readOnly ) return SQLITE_READONLY; if( pBt->page1==0 ){ rc = lockBtree(pBt); if( rc!=SQLITE_OK ){ return rc; |
︙ | ︙ | |||
902 903 904 905 906 907 908 | /* ** Commit the transaction currently in progress. ** ** This will release the write lock on the database file. If there ** are no active cursors, it also releases the read lock. */ | | | | 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 | /* ** Commit the transaction currently in progress. ** ** This will release the write lock on the database file. If there ** are no active cursors, it also releases the read lock. */ static int fileBtreeCommit(Btree *pBt){ int rc; rc = pBt->readOnly ? SQLITE_OK : sqlitepager_commit(pBt->pPager); pBt->inTrans = 0; pBt->inCkpt = 0; unlockBtreeIfUnused(pBt); return rc; } /* ** 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. ** ** This will release the write lock on the database file. If there ** are no active cursors, it also releases the read lock. */ static int fileBtreeRollback(Btree *pBt){ int rc; BtCursor *pCur; if( pBt->inTrans==0 ) return SQLITE_OK; pBt->inTrans = 0; pBt->inCkpt = 0; rc = pBt->readOnly ? SQLITE_OK : sqlitepager_rollback(pBt->pPager); for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){ |
︙ | ︙ | |||
947 948 949 950 951 952 953 | ** main transaction. You must start a transaction before starting a ** checkpoint. The checkpoint is ended automatically if the transaction ** commits or rolls back. ** ** Only one checkpoint may be active at a time. It is an error to try ** to start a new checkpoint if another checkpoint is already active. */ | | | | | 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 | ** main transaction. You must start a transaction before starting a ** checkpoint. The checkpoint is ended automatically if the transaction ** commits or rolls back. ** ** Only one checkpoint may be active at a time. It is an error to try ** to start a new checkpoint if another checkpoint is already active. */ static int fileBtreeBeginCkpt(Btree *pBt){ int rc; if( !pBt->inTrans || pBt->inCkpt ){ return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR; } rc = pBt->readOnly ? SQLITE_OK : sqlitepager_ckpt_begin(pBt->pPager); pBt->inCkpt = 1; return rc; } /* ** Commit a checkpoint to transaction currently in progress. If no ** checkpoint is active, this is a no-op. */ static int fileBtreeCommitCkpt(Btree *pBt){ int rc; if( pBt->inCkpt && !pBt->readOnly ){ rc = sqlitepager_ckpt_commit(pBt->pPager); }else{ rc = SQLITE_OK; } pBt->inCkpt = 0; return rc; } /* ** Rollback the checkpoint to the current transaction. If there ** is no active checkpoint or transaction, this routine is a no-op. ** ** 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. */ static int fileBtreeRollbackCkpt(Btree *pBt){ int rc; BtCursor *pCur; if( pBt->inCkpt==0 || pBt->readOnly ) return SQLITE_OK; rc = sqlitepager_ckpt_rollback(pBt->pPager); for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){ if( pCur->pPage && pCur->pPage->isInit==0 ){ sqlitepager_unref(pCur->pPage); |
︙ | ︙ | |||
1032 1033 1034 1035 1036 1037 1038 | ** should be opened with wrFlag==1 even if they never really intend ** to write. ** ** No checking is done to make sure that page iTable really is the ** root page of a b-tree. If it is not, then the cursor acquired ** will not work correctly. */ | | | 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 | ** should be opened with wrFlag==1 even if they never really intend ** to write. ** ** No checking is done to make sure that page iTable really is the ** root page of a b-tree. If it is not, then the cursor acquired ** will not work correctly. */ static int fileBtreeCursor(Btree *pBt, int iTable, int wrFlag, BtCursor **ppCur){ int rc; BtCursor *pCur, *pRing; if( pBt->page1==0 ){ rc = lockBtree(pBt); if( rc!=SQLITE_OK ){ *ppCur = 0; |
︙ | ︙ | |||
1093 1094 1095 1096 1097 1098 1099 | return rc; } /* ** Close a cursor. The read lock on the database file is released ** when the last cursor is closed. */ | | | 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 | return rc; } /* ** Close a cursor. The read lock on the database file is released ** when the last cursor is closed. */ static int fileBtreeCloseCursor(BtCursor *pCur){ Btree *pBt = pCur->pBt; if( pCur->pPrev ){ pCur->pPrev->pNext = pCur->pNext; }else{ pBt->pCursor = pCur->pNext; } if( pCur->pNext ){ |
︙ | ︙ | |||
1146 1147 1148 1149 1150 1151 1152 | /* ** Set *pSize to the number of bytes of key in the entry the ** cursor currently points to. Always return SQLITE_OK. ** Failure is not possible. If the cursor is not currently ** pointing to an entry (which can happen, for example, if ** the database is empty) then *pSize is set to 0. */ | | | 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 | /* ** Set *pSize to the number of bytes of key in the entry the ** cursor currently points to. Always return SQLITE_OK. ** Failure is not possible. If the cursor is not currently ** pointing to an entry (which can happen, for example, if ** the database is empty) then *pSize is set to 0. */ static int fileBtreeKeySize(BtCursor *pCur, int *pSize){ Cell *pCell; MemPage *pPage; pPage = pCur->pPage; assert( pPage!=0 ); if( pCur->idx >= pPage->nCell ){ *pSize = 0; |
︙ | ︙ | |||
1235 1236 1237 1238 1239 1240 1241 | ** Change: It used to be that the amount returned will be smaller ** than the amount requested if there are not enough bytes in the key ** to satisfy the request. But now, it must be the case that there ** is enough data available to satisfy the request. If not, an exception ** is raised. The change was made in an effort to boost performance ** by eliminating unneeded tests. */ | | | 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 | ** Change: It used to be that the amount returned will be smaller ** than the amount requested if there are not enough bytes in the key ** to satisfy the request. But now, it must be the case that there ** is enough data available to satisfy the request. If not, an exception ** is raised. The change was made in an effort to boost performance ** by eliminating unneeded tests. */ static int fileBtreeKey(BtCursor *pCur, int offset, int amt, char *zBuf){ MemPage *pPage; assert( amt>=0 ); assert( offset>=0 ); assert( pCur->pPage!=0 ); pPage = pCur->pPage; if( pCur->idx >= pPage->nCell ){ |
︙ | ︙ | |||
1257 1258 1259 1260 1261 1262 1263 | /* ** Set *pSize to the number of bytes of data in the entry the ** cursor currently points to. Always return SQLITE_OK. ** Failure is not possible. If the cursor is not currently ** pointing to an entry (which can happen, for example, if ** the database is empty) then *pSize is set to 0. */ | | | 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 | /* ** Set *pSize to the number of bytes of data in the entry the ** cursor currently points to. Always return SQLITE_OK. ** Failure is not possible. If the cursor is not currently ** pointing to an entry (which can happen, for example, if ** the database is empty) then *pSize is set to 0. */ static int fileBtreeDataSize(BtCursor *pCur, int *pSize){ Cell *pCell; MemPage *pPage; pPage = pCur->pPage; assert( pPage!=0 ); if( pCur->idx >= pPage->nCell ){ *pSize = 0; |
︙ | ︙ | |||
1280 1281 1282 1283 1284 1285 1286 | ** Read part of the data associated with cursor pCur. A maximum ** of "amt" bytes will be transfered into zBuf[]. The transfer ** begins at "offset". The number of bytes actually read is ** returned. The amount returned will be smaller than the ** amount requested if there are not enough bytes in the data ** to satisfy the request. */ | | | 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 | ** Read part of the data associated with cursor pCur. A maximum ** of "amt" bytes will be transfered into zBuf[]. The transfer ** begins at "offset". The number of bytes actually read is ** returned. The amount returned will be smaller than the ** amount requested if there are not enough bytes in the data ** to satisfy the request. */ static int fileBtreeData(BtCursor *pCur, int offset, int amt, char *zBuf){ Cell *pCell; MemPage *pPage; assert( amt>=0 ); assert( offset>=0 ); assert( pCur->pPage!=0 ); pPage = pCur->pPage; |
︙ | ︙ | |||
1318 1319 1320 1321 1322 1323 1324 | ** *pRes>0 This means pCur>pKey ** ** When one key is an exact prefix of the other, the shorter key is ** considered less than the longer one. In order to be equal the ** keys must be exactly the same length. (The length of the pCur key ** is the actual key length minus nIgnore bytes.) */ | | | 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 | ** *pRes>0 This means pCur>pKey ** ** When one key is an exact prefix of the other, the shorter key is ** considered less than the longer one. In order to be equal the ** keys must be exactly the same length. (The length of the pCur key ** is the actual key length minus nIgnore bytes.) */ static int fileBtreeKeyCompare( BtCursor *pCur, /* Pointer to entry to compare against */ const void *pKey, /* Key to compare against entry that pCur points to */ int nKey, /* Number of bytes in pKey */ int nIgnore, /* Ignore this many bytes at the end of pCur */ int *pResult /* Write the result here */ ){ Pgno nextPage; |
︙ | ︙ | |||
1517 1518 1519 1520 1521 1522 1523 | return SQLITE_OK; } /* Move the cursor to the first entry in the table. Return SQLITE_OK ** on success. Set *pRes to 0 if the cursor actually points to something ** or set *pRes to 1 if the table is empty. */ | | | | 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 | return SQLITE_OK; } /* Move the cursor to the first entry in the table. Return SQLITE_OK ** on success. Set *pRes to 0 if the cursor actually points to something ** or set *pRes to 1 if the table is empty. */ static int fileBtreeFirst(BtCursor *pCur, int *pRes){ int rc; if( pCur->pPage==0 ) return SQLITE_ABORT; rc = moveToRoot(pCur); if( rc ) return rc; if( pCur->pPage->nCell==0 ){ *pRes = 1; return SQLITE_OK; } *pRes = 0; rc = moveToLeftmost(pCur); pCur->eSkip = SKIP_NONE; return rc; } /* Move the cursor to the last entry in the table. Return SQLITE_OK ** on success. Set *pRes to 0 if the cursor actually points to something ** or set *pRes to 1 if the table is empty. */ static int fileBtreeLast(BtCursor *pCur, int *pRes){ int rc; if( pCur->pPage==0 ) return SQLITE_ABORT; rc = moveToRoot(pCur); if( rc ) return rc; assert( pCur->pPage->isInit ); if( pCur->pPage->nCell==0 ){ *pRes = 1; |
︙ | ︙ | |||
1575 1576 1577 1578 1579 1580 1581 | ** ** *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. */ | > | | | 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 | ** ** *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. */ static int fileBtreeMoveto(BtCursor *pCur, const void *pKey, int nKey, int *pRes){ int rc; if( pCur->pPage==0 ) return SQLITE_ABORT; pCur->eSkip = SKIP_NONE; rc = moveToRoot(pCur); if( rc ) return rc; for(;;){ int lwr, upr; Pgno chldPg; MemPage *pPage = pCur->pPage; int c = -1; /* pRes return if table is empty must be -1 */ lwr = 0; upr = pPage->nCell-1; while( lwr<=upr ){ pCur->idx = (lwr+upr)/2; rc = fileBtreeKeyCompare(pCur, pKey, nKey, 0, &c); if( rc ) return rc; if( c==0 ){ pCur->iMatch = c; if( pRes ) *pRes = 0; return SQLITE_OK; } if( c<0 ){ |
︙ | ︙ | |||
1628 1629 1630 1631 1632 1633 1634 | /* ** Advance the cursor to the next entry in the database. If ** 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. */ | | | 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 | /* ** Advance the cursor to the next entry in the database. If ** 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. */ static int fileBtreeNext(BtCursor *pCur, int *pRes){ int rc; MemPage *pPage = pCur->pPage; assert( pRes!=0 ); if( pPage==0 ){ *pRes = 1; return SQLITE_ABORT; } |
︙ | ︙ | |||
1683 1684 1685 1686 1687 1688 1689 | /* ** Step the cursor to the back to the previous entry in the database. If ** successful then set *pRes=0. If the cursor ** was already pointing to the first entry in the database before ** this routine was called, then set *pRes=1. */ | | | 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 | /* ** Step the cursor to the back to the previous entry in the database. If ** successful then set *pRes=0. If the cursor ** was already pointing to the first entry in the database before ** this routine was called, then set *pRes=1. */ static int fileBtreePrevious(BtCursor *pCur, int *pRes){ int rc; Pgno pgno; MemPage *pPage; pPage = pCur->pPage; if( pPage==0 ){ *pRes = 1; return SQLITE_ABORT; |
︙ | ︙ | |||
2609 2610 2611 2612 2613 2614 2615 | /* ** Insert a new record into the BTree. The key is given by (pKey,nKey) ** and the data is given by (pData,nData). The cursor is used only to ** define what database the record should be inserted into. The cursor ** is left pointing at the new record. */ | | | 2603 2604 2605 2606 2607 2608 2609 2610 2611 2612 2613 2614 2615 2616 2617 | /* ** Insert a new record into the BTree. The key is given by (pKey,nKey) ** and the data is given by (pData,nData). The cursor is used only to ** define what database the record should be inserted into. The cursor ** is left pointing at the new record. */ static int fileBtreeInsert( BtCursor *pCur, /* Insert data into the table of this cursor */ const void *pKey, int nKey, /* The key of the new record */ const void *pData, int nData /* The data of the new record */ ){ Cell newCell; int rc; int loc; |
︙ | ︙ | |||
2635 2636 2637 2638 2639 2640 2641 | assert( !pBt->readOnly ); if( !pCur->wrFlag ){ return SQLITE_PERM; /* Cursor not open for writing */ } if( checkReadLocks(pCur) ){ return SQLITE_LOCKED; /* The table pCur points to has a read lock */ } | | | 2629 2630 2631 2632 2633 2634 2635 2636 2637 2638 2639 2640 2641 2642 2643 | assert( !pBt->readOnly ); if( !pCur->wrFlag ){ return SQLITE_PERM; /* Cursor not open for writing */ } if( checkReadLocks(pCur) ){ return SQLITE_LOCKED; /* The table pCur points to has a read lock */ } rc = fileBtreeMoveto(pCur, pKey, nKey, &loc); if( rc ) return rc; pPage = pCur->pPage; assert( pPage->isInit ); rc = sqlitepager_write(pPage); if( rc ) return rc; rc = fillInCell(pBt, &newCell, pKey, nKey, pData, nData); if( rc ) return rc; |
︙ | ︙ | |||
2677 2678 2679 2680 2681 2682 2683 | ** sqliteBtreeNext() after a delete and the cursor will be left ** pointing to the first entry after the deleted entry. Similarly, ** pCur->eSkip is set to SKIP_PREV is the cursor is left pointing to ** the entry prior to the deleted entry so that a subsequent call to ** sqliteBtreePrevious() will always leave the cursor pointing at the ** entry immediately before the one that was deleted. */ | | | 2671 2672 2673 2674 2675 2676 2677 2678 2679 2680 2681 2682 2683 2684 2685 | ** sqliteBtreeNext() after a delete and the cursor will be left ** pointing to the first entry after the deleted entry. Similarly, ** pCur->eSkip is set to SKIP_PREV is the cursor is left pointing to ** the entry prior to the deleted entry so that a subsequent call to ** sqliteBtreePrevious() will always leave the cursor pointing at the ** entry immediately before the one that was deleted. */ static int fileBtreeDelete(BtCursor *pCur){ MemPage *pPage = pCur->pPage; Cell *pCell; int rc; Pgno pgnoChild; Btree *pBt = pCur->pBt; assert( pPage->isInit ); |
︙ | ︙ | |||
2720 2721 2722 2723 2724 2725 2726 | ** to be a leaf so we can use it. */ BtCursor leafCur; Cell *pNext; int szNext; int notUsed; getTempCursor(pCur, &leafCur); | | | 2714 2715 2716 2717 2718 2719 2720 2721 2722 2723 2724 2725 2726 2727 2728 | ** to be a leaf so we can use it. */ BtCursor leafCur; Cell *pNext; int szNext; int notUsed; getTempCursor(pCur, &leafCur); rc = fileBtreeNext(&leafCur, ¬Used); if( rc!=SQLITE_OK ){ return SQLITE_CORRUPT; } rc = sqlitepager_write(leafCur.pPage); if( rc ) return rc; dropCell(pBt, pPage, pCur->idx, cellSize(pBt, pCell)); pNext = leafCur.pPage->apCell[leafCur.idx]; |
︙ | ︙ | |||
2760 2761 2762 2763 2764 2765 2766 | } /* ** Create a new BTree table. Write into *piTable the page ** number for the root page of the new table. ** ** In the current implementation, BTree tables and BTree indices are the | | > | < < < < < < < < < < < < < | 2754 2755 2756 2757 2758 2759 2760 2761 2762 2763 2764 2765 2766 2767 2768 2769 2770 2771 2772 2773 2774 2775 2776 2777 2778 2779 2780 2781 2782 2783 2784 2785 2786 2787 2788 2789 2790 2791 2792 | } /* ** Create a new BTree table. Write into *piTable the page ** number for the root page of the new table. ** ** In the current implementation, BTree tables and BTree indices are the ** the same. In the future, we may change this so that BTree tables ** are restricted to having a 4-byte integer key and arbitrary data and ** BTree indices are restricted to having an arbitrary key and no data. ** But for now, this routine also serves to create indices. */ static int fileBtreeCreateTable(Btree *pBt, int *piTable){ MemPage *pRoot; Pgno pgnoRoot; int rc; if( !pBt->inTrans ){ /* Must start a transaction first */ return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR; } if( pBt->readOnly ){ return SQLITE_READONLY; } rc = allocatePage(pBt, &pRoot, &pgnoRoot, 0); if( rc ) return rc; assert( sqlitepager_iswriteable(pRoot) ); zeroPage(pBt, pRoot); sqlitepager_unref(pRoot); *piTable = (int)pgnoRoot; return SQLITE_OK; } /* ** Erase the given database page and all its children. Return ** the page to the freelist. */ static int clearDatabasePage(Btree *pBt, Pgno pgno, int freePageFlag){ MemPage *pPage; int rc; |
︙ | ︙ | |||
2840 2841 2842 2843 2844 2845 2846 | sqlitepager_unref(pPage); return rc; } /* ** Delete all information from a single table in the database. */ | | | | | | 2822 2823 2824 2825 2826 2827 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 2862 2863 2864 2865 2866 2867 2868 2869 2870 2871 2872 2873 2874 | sqlitepager_unref(pPage); return rc; } /* ** Delete all information from a single table in the database. */ static int fileBtreeClearTable(Btree *pBt, int iTable){ int rc; BtCursor *pCur; if( !pBt->inTrans ){ return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR; } for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){ if( pCur->pgnoRoot==(Pgno)iTable ){ if( pCur->wrFlag==0 ) return SQLITE_LOCKED; moveToRoot(pCur); } } rc = clearDatabasePage(pBt, (Pgno)iTable, 0); if( rc ){ fileBtreeRollback(pBt); } return rc; } /* ** Erase all information in a table and add the root of the table to ** the freelist. Except, the root of the principle table (the one on ** page 2) is never added to the freelist. */ static int fileBtreeDropTable(Btree *pBt, int iTable){ int rc; MemPage *pPage; BtCursor *pCur; if( !pBt->inTrans ){ return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR; } for(pCur=pBt->pCursor; pCur; pCur=pCur->pNext){ if( pCur->pgnoRoot==(Pgno)iTable ){ return SQLITE_LOCKED; /* Cannot drop a table that has a cursor */ } } rc = sqlitepager_get(pBt->pPager, (Pgno)iTable, (void**)&pPage); if( rc ) return rc; rc = fileBtreeClearTable(pBt, iTable); if( rc ) return rc; if( iTable>2 ){ rc = freePage(pBt, pPage, iTable); }else{ zeroPage(pBt, pPage); } sqlitepager_unref(pPage); |
︙ | ︙ | |||
2991 2992 2993 2994 2995 2996 2997 | return rc; } #endif /* ** Read the meta-information out of a database file. */ | | | | 2973 2974 2975 2976 2977 2978 2979 2980 2981 2982 2983 2984 2985 2986 2987 2988 2989 2990 2991 2992 2993 2994 2995 2996 2997 2998 2999 3000 3001 3002 3003 3004 3005 | return rc; } #endif /* ** Read the meta-information out of a database file. */ static int fileBtreeGetMeta(Btree *pBt, int *aMeta){ PageOne *pP1; int rc; int i; rc = sqlitepager_get(pBt->pPager, 1, (void**)&pP1); if( rc ) return rc; aMeta[0] = SWAB32(pBt, pP1->nFree); for(i=0; i<sizeof(pP1->aMeta)/sizeof(pP1->aMeta[0]); i++){ aMeta[i+1] = SWAB32(pBt, pP1->aMeta[i]); } sqlitepager_unref(pP1); return SQLITE_OK; } /* ** Write meta-information back into the database. */ static int fileBtreeUpdateMeta(Btree *pBt, int *aMeta){ PageOne *pP1; int rc, i; if( !pBt->inTrans ){ return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR; } pP1 = pBt->page1; rc = sqlitepager_write(pP1); |
︙ | ︙ | |||
3035 3036 3037 3038 3039 3040 3041 | ******************************************************************************/ /* ** Print a disassembly of the given page on standard output. This routine ** is used for debugging and testing only. */ #ifdef SQLITE_TEST | | | 3017 3018 3019 3020 3021 3022 3023 3024 3025 3026 3027 3028 3029 3030 3031 | ******************************************************************************/ /* ** Print a disassembly of the given page on standard output. This routine ** is used for debugging and testing only. */ #ifdef SQLITE_TEST static int fileBtreePageDump(Btree *pBt, int pgno, int recursive){ int rc; MemPage *pPage; int i, j; int nFree; u16 idx; char range[20]; unsigned char payload[20]; |
︙ | ︙ | |||
3096 3097 3098 3099 3100 3101 3102 | if( idx!=0 ){ printf("ERROR: next freeblock index out of range: %d\n", idx); } if( recursive && pPage->u.hdr.rightChild!=0 ){ idx = SWAB16(pBt, pPage->u.hdr.firstCell); while( idx>0 && idx<SQLITE_PAGE_SIZE-MIN_CELL_SIZE ){ Cell *pCell = (Cell*)&pPage->u.aDisk[idx]; | | | | 3078 3079 3080 3081 3082 3083 3084 3085 3086 3087 3088 3089 3090 3091 3092 3093 3094 3095 | if( idx!=0 ){ printf("ERROR: next freeblock index out of range: %d\n", idx); } if( recursive && pPage->u.hdr.rightChild!=0 ){ idx = SWAB16(pBt, pPage->u.hdr.firstCell); while( idx>0 && idx<SQLITE_PAGE_SIZE-MIN_CELL_SIZE ){ Cell *pCell = (Cell*)&pPage->u.aDisk[idx]; fileBtreePageDump(pBt, SWAB32(pBt, pCell->h.leftChild), 1); idx = SWAB16(pBt, pCell->h.iNext); } fileBtreePageDump(pBt, SWAB32(pBt, pPage->u.hdr.rightChild), 1); } sqlitepager_unref(pPage); return SQLITE_OK; } #endif #ifdef SQLITE_TEST |
︙ | ︙ | |||
3122 3123 3124 3125 3126 3127 3128 | ** aResult[4] = Number of free bytes on this page ** aResult[5] = Number of free blocks on the page ** aResult[6] = Page number of the left child of this entry ** aResult[7] = Page number of the right child for the whole page ** ** This routine is used for testing and debugging only. */ | | | 3104 3105 3106 3107 3108 3109 3110 3111 3112 3113 3114 3115 3116 3117 3118 | ** aResult[4] = Number of free bytes on this page ** aResult[5] = Number of free blocks on the page ** aResult[6] = Page number of the left child of this entry ** aResult[7] = Page number of the right child for the whole page ** ** This routine is used for testing and debugging only. */ static int fileBtreeCursorDump(BtCursor *pCur, int *aResult){ int cnt, idx; MemPage *pPage = pCur->pPage; Btree *pBt = pCur->pBt; aResult[0] = sqlitepager_pagenumber(pPage); aResult[1] = pCur->idx; aResult[2] = pPage->nCell; if( pCur->idx>=0 && pCur->idx<pPage->nCell ){ |
︙ | ︙ | |||
3154 3155 3156 3157 3158 3159 3160 | #endif #ifdef SQLITE_TEST /* ** Return the pager associated with a BTree. This routine is used for ** testing and debugging only. */ | | | 3136 3137 3138 3139 3140 3141 3142 3143 3144 3145 3146 3147 3148 3149 3150 | #endif #ifdef SQLITE_TEST /* ** Return the pager associated with a BTree. This routine is used for ** testing and debugging only. */ static Pager *fileBtreePager(Btree *pBt){ return pBt->pPager; } #endif /* ** This structure is passed around through all the sanity checking routines ** in order to keep track of some global state information. |
︙ | ︙ | |||
3434 3435 3436 3437 3438 3439 3440 | ** a table. nRoot is the number of entries in aRoot. ** ** If everything checks out, this routine returns NULL. If something is ** amiss, an error message is written into memory obtained from malloc() ** and a pointer to that error message is returned. The calling function ** is responsible for freeing the error message when it is done. */ | | | 3416 3417 3418 3419 3420 3421 3422 3423 3424 3425 3426 3427 3428 3429 3430 | ** a table. nRoot is the number of entries in aRoot. ** ** If everything checks out, this routine returns NULL. If something is ** amiss, an error message is written into memory obtained from malloc() ** and a pointer to that error message is returned. The calling function ** is responsible for freeing the error message when it is done. */ char *fileBtreeIntegrityCheck(Btree *pBt, int *aRoot, int nRoot){ int i; int nRef; IntegrityCk sCheck; nRef = *sqlitepager_stats(pBt->pPager); if( lockBtree(pBt)!=SQLITE_OK ){ return sqliteStrDup("Unable to acquire a read lock on the database"); |
︙ | ︙ | |||
3498 3499 3500 3501 3502 3503 3504 | sqliteFree(sCheck.anRef); return sCheck.zErrMsg; } /* ** Return the full pathname of the underlying database file. */ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 3480 3481 3482 3483 3484 3485 3486 3487 3488 3489 3490 3491 3492 3493 3494 3495 3496 3497 3498 3499 3500 3501 3502 3503 3504 3505 3506 3507 3508 3509 3510 3511 3512 3513 3514 3515 3516 3517 3518 3519 3520 3521 3522 3523 3524 3525 3526 3527 3528 3529 3530 3531 3532 3533 3534 3535 3536 3537 3538 3539 3540 3541 3542 3543 3544 3545 3546 3547 | sqliteFree(sCheck.anRef); return sCheck.zErrMsg; } /* ** Return the full pathname of the underlying database file. */ static const char *fileBtreeGetFilename(Btree *pBt){ assert( pBt->pPager!=0 ); return sqlitepager_filename(pBt->pPager); } /* ** Change the name of the underlying database file. */ static int fileBtreeChangeFilename(Btree *pBt, const char *zNew){ return sqlitepager_rename(pBt->pPager, zNew); } /* ** The following tables contain pointers to all of the interface ** routines for this implementation of the B*Tree backend. To ** substitute a different implemention of the backend, one has merely ** to provide pointers to alternative functions in similar tables. */ static BtOps sqliteBtreeOps = { fileBtreeClose, fileBtreeSetCacheSize, fileBtreeSetSafetyLevel, fileBtreeBeginTrans, fileBtreeCommit, fileBtreeRollback, fileBtreeBeginCkpt, fileBtreeCommitCkpt, fileBtreeRollbackCkpt, fileBtreeCreateTable, fileBtreeCreateTable, /* Really sqliteBtreeCreateIndex() */ fileBtreeDropTable, fileBtreeClearTable, fileBtreeCursor, fileBtreeGetMeta, fileBtreeUpdateMeta, fileBtreeIntegrityCheck, fileBtreeGetFilename, fileBtreeChangeFilename, #ifdef SQLITE_TEST fileBtreePageDump, fileBtreePager #endif }; static BtCursorOps sqliteBtreeCursorOps = { fileBtreeMoveto, fileBtreeDelete, fileBtreeInsert, fileBtreeFirst, fileBtreeLast, fileBtreeNext, fileBtreePrevious, fileBtreeKeySize, fileBtreeKey, fileBtreeKeyCompare, fileBtreeDataSize, fileBtreeData, fileBtreeCloseCursor, #ifdef SQLITE_TEST fileBtreeCursorDump, #endif }; |
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.31 2003/04/16 01:28:16 drh Exp $ */ #ifndef _BTREE_H_ #define _BTREE_H_ /* ** Forward declarations of structure */ |
︙ | ︙ | |||
92 93 94 95 96 97 98 | ** The number of 4-byte "meta" values contained on the first page of each ** database file. */ #define SQLITE_N_BTREE_META 10 int sqliteBtreeOpen(const char *zFilename, int mode, int nPg, Btree **ppBtree); | < | 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | ** The number of 4-byte "meta" values contained on the first page of each ** database file. */ #define SQLITE_N_BTREE_META 10 int sqliteBtreeOpen(const char *zFilename, int mode, int nPg, Btree **ppBtree); #define btOps(pBt) (*((BtOps **)(pBt))) #define btCOps(pCur) (*((BtCursorOps **)(pCur))) #define sqliteBtreeClose(pBt) (btOps(pBt)->Close(pBt)) #define sqliteBtreeSetCacheSize(pBt, sz) (btOps(pBt)->SetCacheSize(pBt, sz)) #define sqliteBtreeSetSafetyLevel(pBt, sl) (btOps(pBt)->SetSafetyLevel(pBt, sl)) #define sqliteBtreeBeginTrans(pBt) (btOps(pBt)->BeginTrans(pBt)) |
︙ | ︙ | |||
139 140 141 142 143 144 145 | #define sqliteBtreeGetMeta(pBt, aMeta) (btOps(pBt)->GetMeta(pBt, aMeta)) #define sqliteBtreeUpdateMeta(pBt, aMeta) (btOps(pBt)->UpdateMeta(pBt, aMeta)) #define sqliteBtreeIntegrityCheck(pBt, aRoot, nRoot)\ (btOps(pBt)->IntegrityCheck(pBt, aRoot, nRoot)) #define sqliteBtreeGetFilename(pBt) (btOps(pBt)->GetFilename(pBt)) #define sqliteBtreeChangeFilename(pBt, zNew)\ (btOps(pBt)->ChangeFilename(pBt, zNew)) | < < < < | > | 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 | #define sqliteBtreeGetMeta(pBt, aMeta) (btOps(pBt)->GetMeta(pBt, aMeta)) #define sqliteBtreeUpdateMeta(pBt, aMeta) (btOps(pBt)->UpdateMeta(pBt, aMeta)) #define sqliteBtreeIntegrityCheck(pBt, aRoot, nRoot)\ (btOps(pBt)->IntegrityCheck(pBt, aRoot, nRoot)) #define sqliteBtreeGetFilename(pBt) (btOps(pBt)->GetFilename(pBt)) #define sqliteBtreeChangeFilename(pBt, zNew)\ (btOps(pBt)->ChangeFilename(pBt, zNew)) #ifdef SQLITE_TEST #define sqliteBtreePageDump(pBt, pgno, recursive)\ (btOps(pBt)->PageDump(pBt, pgno, recursive)) #define sqliteBtreeCursorDump(pCur, aResult)\ (btCOps(pCur)->CursorDump(pCur, aResult)) #define sqliteBtreePager(pBt) (btOps(pBt)->Pager(pBt)) int btree_native_byte_order; #endif /* SQLITE_TEST */ #endif /* _BTREE_H_ */ |
Changes to src/btree_rb.c.
1 2 3 4 5 6 7 8 9 10 11 | /* ** 2003 Feb 4 ** ** 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 20 21 22 23 24 25 | /* ** 2003 Feb 4 ** ** 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_rb.c,v 1.3 2003/04/16 01:28:16 drh Exp $ ** ** This file implements an in-core database using Red-Black balanced ** binary trees. ** ** It was contributed to SQLite by anonymous on 2003-Feb-04 23:24:49 UTC. */ #include "btree.h" #include "sqliteInt.h" #include <assert.h> /* ** Omit this whole file if the SQLITE_OMIT_INMEMORYDB macro is ** defined. This allows a lot of code to be omitted for installations |
︙ | ︙ | |||
123 124 125 126 127 128 129 | BtRbNode *pLeft; /* Nodes left child, or NULL */ BtRbNode *pRight; /* Nodes right child, or NULL */ int nBlackHeight; /* Only used during the red-black integrity check */ }; /* Forward declarations */ | | | | | | | 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 | BtRbNode *pLeft; /* Nodes left child, or NULL */ BtRbNode *pRight; /* Nodes right child, or NULL */ int nBlackHeight; /* Only used during the red-black integrity check */ }; /* Forward declarations */ static int memBtreeMoveto(BtCursor* pCur, const void *pKey, int nKey,int *pRes); static int memBtreeClearTable(Btree* tree, int n); static int memBtreeNext(BtCursor* pCur, int *pRes); static int memBtreeLast(BtCursor* pCur, int *pRes); static int memBtreePrevious(BtCursor* pCur, int *pRes); /* * The key-compare function for the red-black trees. Returns as follows: * * (key1 < key2) -1 * (key1 == key2) 0 * (key1 > key2) 1 |
︙ | ︙ | |||
589 590 591 592 593 594 595 | return SQLITE_OK; } /* * Create a new table in the supplied Btree. Set *n to the new table number. * Return SQLITE_OK if the operation is a success. */ | | < < < < < < < < < < | | | | 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 | return SQLITE_OK; } /* * Create a new table in the supplied Btree. Set *n to the new table number. * Return SQLITE_OK if the operation is a success. */ static int memBtreeCreateTable(Btree* tree, int* n) { assert( tree->eTransState != TRANS_NONE ); *n = tree->next_idx++; btreeCreateTable(tree, *n); /* Set up the rollback structure (if we are not doing this as part of a * rollback) */ if( tree->eTransState != TRANS_ROLLBACK ){ BtRollbackOp *pRollbackOp = sqliteMalloc(sizeof(BtRollbackOp)); pRollbackOp->eOp = ROLLBACK_DROP; pRollbackOp->iTab = *n; btreeLogRollbackOp(tree, pRollbackOp); } return SQLITE_OK; } /* * Delete table n from the supplied Btree. */ static int memBtreeDropTable(Btree* tree, int n) { BtRbTree *pTree; assert( tree->eTransState != TRANS_NONE ); memBtreeClearTable(tree, n); pTree = sqliteHashFind(&tree->tblHash, 0, n); assert(pTree); sqliteFree(pTree); sqliteHashInsert(&tree->tblHash, 0, n, 0); if( tree->eTransState != TRANS_ROLLBACK ){ BtRollbackOp *pRollbackOp = sqliteMalloc(sizeof(BtRollbackOp)); pRollbackOp->eOp = ROLLBACK_CREATE; pRollbackOp->iTab = n; btreeLogRollbackOp(tree, pRollbackOp); } return SQLITE_OK; } static int memBtreeKeyCompare(BtCursor* pCur, const void *pKey, int nKey, int nIgnore, int *pRes) { assert(pCur); if( !pCur->pNode ) { *pRes = -1; } else { |
︙ | ︙ | |||
666 667 668 669 670 671 672 | /* * Get a new cursor for table iTable of the supplied Btree. The wrFlag * parameter is ignored, all cursors are capable of write-operations. * * Note that BtCursor.eSkip and BtCursor.pNode both initialize to 0. */ | | | | 655 656 657 658 659 660 661 662 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 | /* * Get a new cursor for table iTable of the supplied Btree. The wrFlag * parameter is ignored, all cursors are capable of write-operations. * * Note that BtCursor.eSkip and BtCursor.pNode both initialize to 0. */ static int memBtreeCursor(Btree* tree, int iTable, int wrFlag, BtCursor **ppCur) { assert(tree); *ppCur = sqliteMalloc(sizeof(BtCursor)); (*ppCur)->pTree = sqliteHashFind(&tree->tblHash, 0, iTable); (*ppCur)->pBtree = tree; (*ppCur)->iTree = iTable; (*ppCur)->pOps = &sqliteBtreeCursorOps; assert( (*ppCur)->pTree ); return SQLITE_OK; } /* * Insert a new record into the Btree. The key is given by (pKey,nKey) * and the data is given by (pData,nData). The cursor is used only to * define what database the record should be inserted into. The cursor * is left pointing at the new record. * * If the key exists already in the tree, just replace the data. */ static int memBtreeInsert(BtCursor* pCur, const void *pKey, int nKey, const void *pDataInput, int nData) { void * pData; int match; /* It is illegal to call sqliteBtreeInsert() if we are not in a transaction */ assert( pCur->pBtree->eTransState != TRANS_NONE ); |
︙ | ︙ | |||
712 713 714 715 716 717 718 | * If there is no exact match, then the cursor points at what would be either * the predecessor (match == -1) or successor (match == 1) of the * searched-for key, were it to be inserted. The new node becomes a child of * this node. * * The new node is initially red. */ | | | 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 | * If there is no exact match, then the cursor points at what would be either * the predecessor (match == -1) or successor (match == 1) of the * searched-for key, were it to be inserted. The new node becomes a child of * this node. * * The new node is initially red. */ memBtreeMoveto( pCur, pKey, nKey, &match); if( match ){ BtRbNode *pNode = sqliteMalloc(sizeof(BtRbNode)); pNode->nKey = nKey; pNode->pKey = sqliteMalloc(nKey); memcpy(pNode->pKey, pKey, nKey); pNode->nData = nData; pNode->pData = pData; |
︙ | ︙ | |||
796 797 798 799 800 801 802 | ** ** *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. */ | | | 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 | ** ** *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. */ static int memBtreeMoveto(BtCursor* pCur, const void *pKey, int nKey, int *pRes) { BtRbNode *pTmp = 0; pCur->pNode = pCur->pTree->pHead; *pRes = -1; while( pCur->pNode && *pRes ) { *pRes = key_compare(pCur->pNode->pKey, pCur->pNode->nKey, pKey, nKey); |
︙ | ︙ | |||
840 841 842 843 844 845 846 | ** sqliteBtreeNext() after a delete and the cursor will be left ** pointing to the first entry after the deleted entry. Similarly, ** pCur->eSkip is set to SKIP_PREV is the cursor is left pointing to ** the entry prior to the deleted entry so that a subsequent call to ** sqliteBtreePrevious() will always leave the cursor pointing at the ** entry immediately before the one that was deleted. */ | | | 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 | ** sqliteBtreeNext() after a delete and the cursor will be left ** pointing to the first entry after the deleted entry. Similarly, ** pCur->eSkip is set to SKIP_PREV is the cursor is left pointing to ** the entry prior to the deleted entry so that a subsequent call to ** sqliteBtreePrevious() will always leave the cursor pointing at the ** entry immediately before the one that was deleted. */ static int memBtreeDelete(BtCursor* pCur) { BtRbNode *pZ; /* The one being deleted */ BtRbNode *pChild; /* The child of the spliced out node */ /* It is illegal to call sqliteBtreeDelete() if we are not in a transaction */ assert( pCur->pBtree->eTransState != TRANS_NONE ); |
︙ | ︙ | |||
876 877 878 879 880 881 882 | * If pZ has no children or one child, then splice out pZ. If pZ has two * children, splice out the successor of pZ and replace the key and data of * pZ with the key and data of the spliced out successor. */ if( pZ->pLeft && pZ->pRight ){ BtRbNode *pTmp; int dummy; pCur->eSkip = SKIP_NONE; | | | | | | 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 895 896 897 898 899 900 | * If pZ has no children or one child, then splice out pZ. If pZ has two * children, splice out the successor of pZ and replace the key and data of * pZ with the key and data of the spliced out successor. */ if( pZ->pLeft && pZ->pRight ){ BtRbNode *pTmp; int dummy; pCur->eSkip = SKIP_NONE; memBtreeNext(pCur, &dummy); assert( dummy == 0 ); if( pCur->pBtree->eTransState == TRANS_ROLLBACK ){ sqliteFree(pZ->pKey); sqliteFree(pZ->pData); } pZ->pData = pCur->pNode->pData; pZ->nData = pCur->pNode->nData; pZ->pKey = pCur->pNode->pKey; pZ->nKey = pCur->pNode->nKey; pTmp = pZ; pZ = pCur->pNode; pCur->pNode = pTmp; pCur->eSkip = SKIP_NEXT; }else{ int res; pCur->eSkip = SKIP_NONE; memBtreeNext(pCur, &res); pCur->eSkip = SKIP_NEXT; if( res ){ memBtreeLast(pCur, &res); memBtreePrevious(pCur, &res); pCur->eSkip = SKIP_PREV; } if( pCur->pBtree->eTransState == TRANS_ROLLBACK ){ sqliteFree(pZ->pKey); sqliteFree(pZ->pData); } } |
︙ | ︙ | |||
939 940 941 942 943 944 945 | sqliteFree(pZ); return SQLITE_OK; } /* * Empty table n of the Btree. */ | | | 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 | sqliteFree(pZ); return SQLITE_OK; } /* * Empty table n of the Btree. */ static int memBtreeClearTable(Btree* tree, int n) { BtRbTree *pTree; BtRbNode *pNode; pTree = sqliteHashFind(&tree->tblHash, 0, n); assert(pTree); |
︙ | ︙ | |||
983 984 985 986 987 988 989 | } } pTree->pHead = 0; return SQLITE_OK; } | | | | | 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 | } } pTree->pHead = 0; return SQLITE_OK; } static int memBtreeFirst(BtCursor* pCur, int *pRes) { if( pCur->pTree->pHead ){ pCur->pNode = pCur->pTree->pHead; while( pCur->pNode->pLeft ){ pCur->pNode = pCur->pNode->pLeft; } } if( pCur->pNode ){ *pRes = 0; }else{ *pRes = 1; } pCur->eSkip = SKIP_NONE; return SQLITE_OK; } static int memBtreeLast(BtCursor* pCur, int *pRes) { if( pCur->pTree->pHead ){ pCur->pNode = pCur->pTree->pHead; while( pCur->pNode->pRight ){ pCur->pNode = pCur->pNode->pRight; } } if( pCur->pNode ){ *pRes = 0; }else{ *pRes = 1; } pCur->eSkip = SKIP_NONE; return SQLITE_OK; } static int memBtreeNext(BtCursor* pCur, int *pRes) { if( pCur->pNode && pCur->eSkip != SKIP_NEXT ){ if( pCur->pNode->pRight ){ pCur->pNode = pCur->pNode->pRight; while( pCur->pNode->pLeft ) pCur->pNode = pCur->pNode->pLeft; }else{ |
︙ | ︙ | |||
1044 1045 1046 1047 1048 1049 1050 | }else{ *pRes = 0; } return SQLITE_OK; } | | | 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 | }else{ *pRes = 0; } return SQLITE_OK; } static int memBtreePrevious(BtCursor* pCur, int *pRes) { if( pCur->pNode && pCur->eSkip != SKIP_PREV ){ if( pCur->pNode->pLeft ){ pCur->pNode = pCur->pNode->pLeft; while( pCur->pNode->pRight ) pCur->pNode = pCur->pNode->pRight; }else{ |
︙ | ︙ | |||
1071 1072 1073 1074 1075 1076 1077 | }else{ *pRes = 0; } return SQLITE_OK; } | | | | | | | | | | | | | | | | 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 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 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 | }else{ *pRes = 0; } return SQLITE_OK; } static int memBtreeKeySize(BtCursor* pCur, int *pSize) { if( pCur->pNode ){ *pSize = pCur->pNode->nKey; }else{ *pSize = 0; } return SQLITE_OK; } static int memBtreeKey(BtCursor* pCur, int offset, int amt, char *zBuf) { if( !pCur->pNode ) return 0; if( !pCur->pNode->pKey || ((amt + offset) <= pCur->pNode->nKey) ){ memcpy(zBuf, pCur->pNode->pKey+offset, amt); return amt; }else{ memcpy(zBuf, pCur->pNode->pKey+offset ,pCur->pNode->nKey-offset); return pCur->pNode->nKey-offset; } assert(0); } static int memBtreeDataSize(BtCursor* pCur, int *pSize) { if( pCur->pNode ){ *pSize = pCur->pNode->nData; }else{ *pSize = 0; } return SQLITE_OK; } static int memBtreeData(BtCursor *pCur, int offset, int amt, char *zBuf) { if( !pCur->pNode ) return 0; if( (amt + offset) <= pCur->pNode->nData ){ memcpy(zBuf, pCur->pNode->pData+offset, amt); return amt; }else{ memcpy(zBuf, pCur->pNode->pData+offset ,pCur->pNode->nData-offset); return pCur->pNode->nData-offset; } assert(0); } static int memBtreeCloseCursor(BtCursor* pCur) { sqliteFree(pCur); return SQLITE_OK; } static int memBtreeGetMeta(Btree* tree, int* aMeta) { memcpy( aMeta, tree->aMetaData, sizeof(int) * SQLITE_N_BTREE_META ); return SQLITE_OK; } static int memBtreeUpdateMeta(Btree* tree, int* aMeta) { memcpy( tree->aMetaData, aMeta, sizeof(int) * SQLITE_N_BTREE_META ); return SQLITE_OK; } /* * Check that each table in the Btree meets the requirements for a red-black * binary tree. If an error is found, return an explanation of the problem in * memory obtained from sqliteMalloc(). Parameters aRoot and nRoot are ignored. */ static char *memBtreeIntegrityCheck(Btree* tree, int* aRoot, int nRoot) { char * msg = 0; HashElem *p; for(p=sqliteHashFirst(&tree->tblHash); p; p=sqliteHashNext(p)){ BtRbTree *pTree = sqliteHashData(p); check_redblack_tree(pTree, &msg); } return msg; } /* * Close the supplied Btree. Delete everything associated with it. */ static int memBtreeClose(Btree* tree) { HashElem *p; for(p=sqliteHashFirst(&tree->tblHash); p; p=sqliteHashNext(p)){ tree->eTransState = TRANS_ROLLBACK; memBtreeClearTable(tree, sqliteHashKeysize(p)); sqliteFree(sqliteHashData(p)); } sqliteFree(tree); return SQLITE_OK; } static int memBtreeSetCacheSize(Btree* tree, int sz) { return SQLITE_OK; } static int memBtreeSetSafetyLevel(Btree *pBt, int level){ return SQLITE_OK; } static int memBtreeBeginTrans(Btree* tree) { if( tree->eTransState != TRANS_NONE ) return SQLITE_ERROR; assert( tree->pTransRollback == 0 ); tree->eTransState = TRANS_INTRANSACTION; return SQLITE_OK; } static int memBtreeCommit(Btree* tree) { /* Just delete pTransRollback and pCheckRollback */ BtRollbackOp *pOp, *pTmp; pOp = tree->pCheckRollback; while( pOp ){ pTmp = pOp->pNext; sqliteFree(pOp->pData); |
︙ | ︙ | |||
1231 1232 1233 1234 1235 1236 1237 | while( pList ){ switch( pList->eOp ){ case ROLLBACK_INSERT: cur.pTree = sqliteHashFind( &pBtree->tblHash, 0, pList->iTab ); assert(cur.pTree); cur.iTree = pList->iTab; cur.eSkip = SKIP_NONE; | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 | while( pList ){ switch( pList->eOp ){ case ROLLBACK_INSERT: cur.pTree = sqliteHashFind( &pBtree->tblHash, 0, pList->iTab ); assert(cur.pTree); cur.iTree = pList->iTab; cur.eSkip = SKIP_NONE; memBtreeInsert( &cur, pList->pKey, pList->nKey, pList->pData, pList->nData ); break; case ROLLBACK_DELETE: cur.pTree = sqliteHashFind( &pBtree->tblHash, 0, pList->iTab ); assert(cur.pTree); cur.iTree = pList->iTab; cur.eSkip = SKIP_NONE; memBtreeMoveto(&cur, pList->pKey, pList->nKey, &res); assert(res == 0); memBtreeDelete( &cur ); break; case ROLLBACK_CREATE: btreeCreateTable(pBtree, pList->iTab); break; case ROLLBACK_DROP: memBtreeDropTable(pBtree, pList->iTab); break; default: assert(0); } sqliteFree(pList->pKey); sqliteFree(pList->pData); pTmp = pList->pNext; sqliteFree(pList); pList = pTmp; } } static int memBtreeRollback(Btree* tree) { tree->eTransState = TRANS_ROLLBACK; execute_rollback_list(tree, tree->pCheckRollback); execute_rollback_list(tree, tree->pTransRollback); tree->pTransRollback = 0; tree->pCheckRollback = 0; tree->pCheckRollbackTail = 0; tree->eTransState = TRANS_NONE; return SQLITE_OK; } static int memBtreeBeginCkpt(Btree* tree) { if( tree->eTransState != TRANS_INTRANSACTION ) return SQLITE_ERROR; assert( tree->pCheckRollback == 0 ); assert( tree->pCheckRollbackTail == 0 ); tree->eTransState = TRANS_INCHECKPOINT; return SQLITE_OK; } static int memBtreeCommitCkpt(Btree* tree) { if( tree->eTransState == TRANS_INCHECKPOINT ){ if( tree->pCheckRollback ){ tree->pCheckRollbackTail->pNext = tree->pTransRollback; tree->pTransRollback = tree->pCheckRollback; tree->pCheckRollback = 0; tree->pCheckRollbackTail = 0; } tree->eTransState = TRANS_INTRANSACTION; } return SQLITE_OK; } static int memBtreeRollbackCkpt(Btree* tree) { if( tree->eTransState != TRANS_INCHECKPOINT ) return SQLITE_OK; tree->eTransState = TRANS_ROLLBACK; execute_rollback_list(tree, tree->pCheckRollback); tree->pCheckRollback = 0; tree->pCheckRollbackTail = 0; tree->eTransState = TRANS_INTRANSACTION; return SQLITE_OK; return SQLITE_OK; } #ifdef SQLITE_TEST static int memBtreePageDump(Btree* tree, int pgno, int rec) { assert(!"Cannot call sqliteBtreePageDump"); return SQLITE_OK; } static int memBtreeCursorDump(BtCursor* pCur, int* aRes) { assert(!"Cannot call sqliteBtreeCursorDump"); return SQLITE_OK; } static struct Pager *memBtreePager(Btree* tree) { assert(!"Cannot call sqliteBtreePager"); return SQLITE_OK; } #endif /* ** Return the full pathname of the underlying database file. */ static const char *memBtreeGetFilename(Btree *pBt){ return ":memory:"; } /* ** Change the name of the underlying database file. */ static int memBtreeChangeFilename(Btree *pBt, const char *zNew){ return SQLITE_OK; } static BtOps sqliteBtreeOps = { memBtreeClose, memBtreeSetCacheSize, memBtreeSetSafetyLevel, memBtreeBeginTrans, memBtreeCommit, memBtreeRollback, memBtreeBeginCkpt, memBtreeCommitCkpt, memBtreeRollbackCkpt, memBtreeCreateTable, memBtreeCreateTable, memBtreeDropTable, memBtreeClearTable, memBtreeCursor, memBtreeGetMeta, memBtreeUpdateMeta, memBtreeIntegrityCheck, memBtreeGetFilename, memBtreeChangeFilename, #ifdef SQLITE_TEST memBtreePageDump, memBtreePager #endif }; static BtCursorOps sqliteBtreeCursorOps = { memBtreeMoveto, memBtreeDelete, memBtreeInsert, memBtreeFirst, memBtreeLast, memBtreeNext, memBtreePrevious, memBtreeKeySize, memBtreeKey, memBtreeKeyCompare, memBtreeDataSize, memBtreeData, memBtreeCloseCursor, #ifdef SQLITE_TEST memBtreeCursorDump, #endif }; #endif /* SQLITE_OMIT_INMEMORYDB */ |
Changes to src/main.c.
︙ | ︙ | |||
10 11 12 13 14 15 16 | ** ************************************************************************* ** Main file for the SQLite library. The routines in this file ** implement the programmer interface to the library. Routines in ** other files are for internal use by SQLite and should not be ** accessed by users of the library. ** | | | 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | ** ************************************************************************* ** Main file for the SQLite library. The routines in this file ** implement the programmer interface to the library. Routines in ** other files are for internal use by SQLite and should not be ** accessed by users of the library. ** ** $Id: main.c,v 1.124 2003/04/16 01:28:16 drh Exp $ */ #include "sqliteInt.h" #include "os.h" #include <ctype.h> /* ** A pointer to this structure is used to communicate information |
︙ | ︙ | |||
422 423 424 425 426 427 428 | sqliteHashInit(&db->aDb[i].tblHash, SQLITE_HASH_STRING, 0); sqliteHashInit(&db->aDb[i].idxHash, SQLITE_HASH_STRING, 0); sqliteHashInit(&db->aDb[i].trigHash, SQLITE_HASH_STRING, 0); sqliteHashInit(&db->aDb[i].aFKey, SQLITE_HASH_STRING, 1); } /* Open the backend database driver */ | | | 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 | sqliteHashInit(&db->aDb[i].tblHash, SQLITE_HASH_STRING, 0); sqliteHashInit(&db->aDb[i].idxHash, SQLITE_HASH_STRING, 0); sqliteHashInit(&db->aDb[i].trigHash, SQLITE_HASH_STRING, 0); sqliteHashInit(&db->aDb[i].aFKey, SQLITE_HASH_STRING, 1); } /* Open the backend database driver */ rc = sqliteBtreeFactory(db, zFilename, 0, MAX_PAGES, &db->aDb[0].pBt); if( rc!=SQLITE_OK ){ switch( rc ){ default: { sqliteSetString(pzErrMsg, "unable to open database: ", zFilename, 0); } } sqliteFree(db); |
︙ | ︙ | |||
1061 1062 1063 1064 1065 1066 1067 | ** driver. If zFilename is the name of a file, then that file is ** opened and used. If zFilename is the magic name ":memory:" then ** the database is stored in memory (and is thus forgotten as soon as ** the connection is closed.) If zFilename is NULL then the database ** is for temporary use only and is deleted as soon as the connection ** is closed. ** | < < | 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 | ** driver. If zFilename is the name of a file, then that file is ** opened and used. If zFilename is the magic name ":memory:" then ** the database is stored in memory (and is thus forgotten as soon as ** the connection is closed.) If zFilename is NULL then the database ** is for temporary use only and is deleted as soon as the connection ** is closed. ** ** A temporary database can be either a disk file (that is automatically ** deleted when the file is closed) or a set of red-black trees held in memory, ** depending on the values of the TEMP_STORE compile-time macro and the ** db->temp_store variable, according to the following chart: ** ** TEMP_STORE db->temp_store Location of temporary database ** ---------- -------------- ------------------------------ |
︙ | ︙ |