Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Add hooks to run the "lsmtest" tree-structure tests and performance comparisons on the btree module. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
8140c0abefd0a9889c26c0235c875b70 |
User & Date: | dan 2013-10-08 20:37:21.156 |
Context
2013-10-09
| ||
20:14 | Add code to deal with large values (those that will not fit on a leaf) to the btree code. Large keys are still not working. check-in: 2bd81969a6 user: dan tags: trunk | |
2013-10-08
| ||
20:37 | Add hooks to run the "lsmtest" tree-structure tests and performance comparisons on the btree module. check-in: 8140c0abef user: dan tags: trunk | |
17:38 | Fix another bug in b-tree rebalancing. check-in: f4df828793 user: dan tags: trunk | |
Changes
Changes to lsm-test/lsmtest_tdb.c.
︙ | ︙ | |||
677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 | *ppDb = (TestDb *)pDb; return 0; } /* ** End wrapper for SQLite. *************************************************************************/ /************************************************************************* ** Begin exported functions. */ static struct Lib { const char *zName; const char *zDefaultDb; int (*xOpen)(const char *zFilename, int bClear, TestDb **ppDb); } aLib[] = { { "sqlite3", "testdb.sqlite", sql_open }, { "lsm_small", "testdb.lsm_small", test_lsm_small_open }, { "lsm_lomem", "testdb.lsm_lomem", test_lsm_lomem_open }, #ifdef HAVE_ZLIB { "lsm_zip", "testdb.lsm_zip", test_lsm_zip_open }, #endif { "lsm", "testdb.lsm", test_lsm_open }, | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 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 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 | *ppDb = (TestDb *)pDb; return 0; } /* ** End wrapper for SQLite. *************************************************************************/ /************************************************************************* ** Begin bt wrapper. */ #include "bt.h" typedef struct BtDb BtDb; struct BtDb { TestDb base; bt_db *pBt; /* Space for bt_fetch() results */ u8 *aBuffer; int nBuffer; }; int bt_close(TestDb *pTestDb){ BtDb *p = (BtDb*)pTestDb; free(p->aBuffer); return sqlite4BtClose(p->pBt); } int bt_write(TestDb *pTestDb, void *pK, int nK, void *pV, int nV){ BtDb *p = (BtDb*)pTestDb; int iLevel; int rc = SQLITE4_OK; iLevel = sqlite4BtTransactionLevel(p->pBt); if( iLevel<2 ){ rc = sqlite4BtBegin(p->pBt, 2); } rc = sqlite4BtReplace(p->pBt, pK, nK, pV, nV); if( rc==SQLITE4_OK && iLevel<2 ){ rc = sqlite4BtCommit(p->pBt, iLevel); } return rc; } int bt_delete(TestDb *pTestDb, void *pK, int nK){ return bt_write(pTestDb, pK, nK, 0, -1); } int bt_delete_range( TestDb *pTestDb, void *pKey1, int nKey1, void *pKey2, int nKey2 ){ return SQLITE4_OK; } int bt_fetch(TestDb *pTestDb, void *pK, int nK, void **ppVal, int *pnVal){ BtDb *p = (BtDb*)pTestDb; bt_cursor *pCsr = 0; int iLevel; int rc = SQLITE4_OK; iLevel = sqlite4BtTransactionLevel(p->pBt); if( iLevel==0 ){ rc = sqlite4BtBegin(p->pBt, 1); if( rc!=SQLITE4_OK ) return rc; } rc = sqlite4BtCsrOpen(p->pBt, 0, &pCsr); if( rc==SQLITE4_OK ){ rc = sqlite4BtCsrSeek(pCsr, pK, nK, BT_SEEK_EQ); if( rc==SQLITE4_OK ){ const void *pV = 0; int nV = 0; rc = sqlite4BtCsrData(pCsr, 0, -1, &pV, &nV); if( rc==SQLITE4_OK ){ if( nV>p->nBuffer ){ free(p->aBuffer); p->aBuffer = (u8*)malloc(nV*2); p->nBuffer = nV*2; } memcpy(p->aBuffer, pV, nV); *pnVal = nV; *ppVal = (void*)(p->aBuffer); } }else if( rc==SQLITE4_INEXACT || rc==SQLITE4_NOTFOUND ){ *ppVal = 0; *pnVal = -1; rc = SQLITE4_OK; } sqlite4BtCsrClose(pCsr); } if( iLevel==0 ) sqlite4BtCommit(p->pBt, 0); return rc; } static int bt_scan( TestDb *pTestDb, void *pCtx, int bReverse, void *pFirst, int nFirst, void *pLast, int nLast, void (*xCallback)(void *, void *, int , void *, int) ){ BtDb *p = (BtDb*)pTestDb; bt_cursor *pCsr = 0; int rc; rc = sqlite4BtCsrOpen(p->pBt, 0, &pCsr); if( rc==SQLITE4_OK ){ rc = sqlite4BtCsrSeek(pCsr, pFirst, nFirst, BT_SEEK_GE); if( rc==SQLITE4_INEXACT ) rc = SQLITE4_OK; while( rc==SQLITE4_OK ){ const void *pK = 0; int nK = 0; const void *pV = 0; int nV = 0; rc = sqlite4BtCsrKey(pCsr, &pK, &nK); if( rc==SQLITE4_OK ){ rc = sqlite4BtCsrData(pCsr, 0, -1, &pV, &nV); } if( pLast && rc==SQLITE4_OK ){ int nCmp = MAX(nK, nLast); int res; res = memcmp(pLast, pK, nCmp); if( res<0 || (res==0 && nK>nLast) ) break; } xCallback(pCtx, (void*)pK, nK, (void*)pV, nV); rc = sqlite4BtCsrNext(pCsr); } if( rc==SQLITE4_NOTFOUND ) rc = SQLITE4_OK; sqlite4BtCsrClose(pCsr); } return rc; } int bt_open(const char *zFilename, int bClear, TestDb **ppDb){ static const DatabaseMethods SqlMethods = { bt_close, bt_write, bt_delete, 0, bt_fetch, bt_scan, 0, 0, 0 }; BtDb *p = 0; bt_db *pBt = 0; int rc; sqlite4_env *pEnv = sqlite4_env_default(); if( bClear && zFilename && zFilename[0] ){ unlink(zFilename); } rc = sqlite4BtNew(pEnv, sizeof(BtDb), &pBt); if( rc==SQLITE4_OK ){ p = (BtDb*)sqlite4BtExtra(pBt); p->base.pMethods = &SqlMethods; p->pBt = pBt; rc = sqlite4BtOpen(pBt, zFilename); } if( rc!=SQLITE4_OK && p ){ bt_close(&p->base); } *ppDb = &p->base; return rc; } /* ** End wrapper for bt. *************************************************************************/ /************************************************************************* ** Begin exported functions. */ static struct Lib { const char *zName; const char *zDefaultDb; int (*xOpen)(const char *zFilename, int bClear, TestDb **ppDb); } aLib[] = { { "bt", "testdb.bt", bt_open }, { "sqlite3", "testdb.sqlite", sql_open }, { "lsm_small", "testdb.lsm_small", test_lsm_small_open }, { "lsm_lomem", "testdb.lsm_lomem", test_lsm_lomem_open }, #ifdef HAVE_ZLIB { "lsm_zip", "testdb.lsm_zip", test_lsm_zip_open }, #endif { "lsm", "testdb.lsm", test_lsm_open }, |
︙ | ︙ |
Changes to src/bt_main.c.
︙ | ︙ | |||
25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | #define BT_PGFLAGS_INTERNAL 0x01 /* True for non-leaf nodes */ struct bt_db { sqlite4_env *pEnv; /* SQLite environment */ BtPager *pPager; /* Underlying page-based database */ }; struct bt_cursor { bt_db *pDb; /* Database that owns this cursor */ int nPg; /* Number of valid entries in apPage[] */ int aiCell[BT_MAX_DEPTH]; /* Current cell of each apPage[] entry */ BtPage *apPage[BT_MAX_DEPTH]; /* All pages from root to current leaf */ }; #ifndef btErrorBkpt int btErrorBkpt(int rc){ static int error_cnt = 0; error_cnt++; return rc; } #endif /* | > > > | | > > > > > > > > > > > > > | 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 | #define BT_PGFLAGS_INTERNAL 0x01 /* True for non-leaf nodes */ struct bt_db { sqlite4_env *pEnv; /* SQLite environment */ BtPager *pPager; /* Underlying page-based database */ }; /* ** Database cursor handle. */ struct bt_cursor { bt_db *pDb; /* Database that owns this cursor */ int nPg; /* Number of valid entries in apPage[] */ int aiCell[BT_MAX_DEPTH]; /* Current cell of each apPage[] entry */ BtPage *apPage[BT_MAX_DEPTH]; /* All pages from root to current leaf */ }; #ifndef btErrorBkpt int btErrorBkpt(int rc){ static int error_cnt = 0; error_cnt++; return rc; } #endif /* ** Interpret the first 4 bytes of the buffer indicated by the first ** parameter as a 32-bit unsigned big-endian integer. */ static u32 btGetU32(const u8 *a){ return ((u32)a[0] << 24) + ((u32)a[1] << 16) + ((u32)a[2] << 8) + ((u32)a[3]); } /* ** Interpret the first 2 bytes of the buffer indicated by the first ** parameter as a 16-bit unsigned big-endian integer. */ static u16 btGetU16(const u8 *a){ return ((u32)a[0] << 8) + (u32)a[1]; } /* ** Write the value passed as the second argument to the buffer passed ** as the first. Formatted as an unsigned 16-bit big-endian integer. */ static void btPutU16(u8 *a, u16 i){ a[0] = (u8)((i>>8) & 0xFF); a[1] = (u8)((i>>0) & 0xFF); } /* ** Write the value passed as the second argument to the buffer passed ** as the first. Formatted as an unsigned 32-bit big-endian integer. */ static void btPutU32(u8 *a, u32 i){ a[0] = (u8)((i>>24) & 0xFF); a[1] = (u8)((i>>16) & 0xFF); a[2] = (u8)((i>>8) & 0xFF); a[3] = (u8)((i>>0) & 0xFF); } |
︙ | ︙ | |||
195 196 197 198 199 200 201 202 203 204 205 206 207 208 | if( rc==SQLITE4_OK ){ pCsr->nPg++; } } return rc; } static int btCsrAscend(bt_cursor *pCsr){ if( pCsr->nPg>0 ){ pCsr->nPg--; sqlite4BtPageRelease(pCsr->apPage[pCsr->nPg]); } return (pCsr->nPg==0 ? SQLITE4_NOTFOUND : SQLITE4_OK); } | > > > > > | 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 | if( rc==SQLITE4_OK ){ pCsr->nPg++; } } return rc; } /* ** Move the cursor from the current page to the parent. Return ** SQLITE4_NOTFOUND if the cursor already points to the root page, ** or SQLITE4_OK otherwise. */ static int btCsrAscend(bt_cursor *pCsr){ if( pCsr->nPg>0 ){ pCsr->nPg--; sqlite4BtPageRelease(pCsr->apPage[pCsr->nPg]); } return (pCsr->nPg==0 ? SQLITE4_NOTFOUND : SQLITE4_OK); } |
︙ | ︙ | |||
1262 1263 1264 1265 1266 1267 1268 | } } rc = btSetChildPgno( pDb, pPar, iSib+ctx.nIn-1, sqlite4BtPagePgno(ctx.apPg[ctx.nOut-1]) ); if( rc==SQLITE4_OK ){ | | | 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 | } } rc = btSetChildPgno( pDb, pPar, iSib+ctx.nIn-1, sqlite4BtPagePgno(ctx.apPg[ctx.nOut-1]) ); if( rc==SQLITE4_OK ){ btCsrAscend(pCsr); rc = btDeleteFromPage(pCsr, ctx.nIn-1); } iPg = pCsr->nPg; if( rc==SQLITE4_OK && ctx.nOut>1 ){ rc = btInsertAndBalance(pCsr, ctx.nOut-1, ctx.aPCell); } if( rc==SQLITE4_OK && iPg==pCsr->nPg ){ |
︙ | ︙ | |||
1537 1538 1539 1540 1541 1542 1543 | btCsrSetup(db, &csr); rc = btCsrSeek(&csr, pK, nK, BT_SEEK_GE, 1); if( rc==SQLITE4_OK ){ /* The cursor currently points to an entry with key pK/nK. This call ** should therefore replace that entry. So delete it and then re-seek ** the cursor. */ rc = sqlite4BtDelete(&csr); | > | > < | | 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 | btCsrSetup(db, &csr); rc = btCsrSeek(&csr, pK, nK, BT_SEEK_GE, 1); if( rc==SQLITE4_OK ){ /* The cursor currently points to an entry with key pK/nK. This call ** should therefore replace that entry. So delete it and then re-seek ** the cursor. */ rc = sqlite4BtDelete(&csr); if( rc==SQLITE4_OK && nV>=0 ){ rc = btCsrSeek(&csr, pK, nK, BT_SEEK_GE, 1); if( rc==SQLITE4_OK ) rc = btErrorBkpt(SQLITE4_CORRUPT); } } if( nV>=0 && (rc==SQLITE4_NOTFOUND || rc==SQLITE4_INEXACT) ){ /* Insert the new KV pair into the current leaf. */ KeyValue kv; kv.pgno = 0; kv.pK = pK; kv.nK = nK; kv.pV = pV; kv.nV = nV; rc = btInsertAndBalance(&csr, 1, &kv); } |
︙ | ︙ |