Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Fix further bugs in in-memory tree. Progress on writing range-deletes into the database file. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | range-delete |
Files: | files | file ages | folders |
SHA1: |
9081b1c92cf5e6e632538a337815932c |
User & Date: | dan 2012-10-09 19:55:49.677 |
Context
2012-10-10
| ||
18:10 | Fixes for range-delete and seek operations. check-in: 1ff4639070 user: dan tags: range-delete | |
2012-10-09
| ||
19:55 | Fix further bugs in in-memory tree. Progress on writing range-deletes into the database file. check-in: 9081b1c92c user: dan tags: range-delete | |
2012-10-08
| ||
17:08 | Fixes for range-deletes on the in-memory tree structure. check-in: 9879e2a63d user: dan tags: range-delete | |
Changes
Changes to lsm-test/lsmtest1.c.
︙ | ︙ | |||
344 345 346 347 348 349 350 351 352 353 354 | doDataTest1(zSystem, &aTest[i], pRc); } testFree(zName); } } static void testCompareDb( TestDb *pControl, TestDb *pDb, int *pRc ){ | > > > > > > > > > > > > > > > | | > > > > > > > > > | 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 | doDataTest1(zSystem, &aTest[i], pRc); } testFree(zName); } } static void testCompareDb( Datasource *pData, int nData, int iSeed, TestDb *pControl, TestDb *pDb, int *pRc ){ int iKey1; int iKey2; void *pKey1; int nKey1; /* Start key */ void *pKey2; int nKey2; /* Final key */ iKey1 = testPrngValue(iSeed) % nData; iKey2 = testPrngValue(iSeed+1) % nData; testDatasourceEntry(pData, iKey1, &pKey2, &nKey1, 0, 0); pKey1 = testMalloc(nKey1+1); memcpy(pKey1, pKey2, nKey1+1); testDatasourceEntry(pData, iKey2, &pKey2, &nKey2, 0, 0); testScanCompare(pControl, pDb, 0, 0, 0, 0, 0, pRc); testScanCompare(pControl, pDb, 1, 0, 0, 0, 0, pRc); testScanCompare(pControl, pDb, 0, 0, 0, pKey2, nKey2, pRc); testScanCompare(pControl, pDb, 0, pKey1, nKey1, 0, 0, pRc); testScanCompare(pControl, pDb, 0, pKey1, nKey1, pKey2, nKey2, pRc); testScanCompare(pControl, pDb, 1, 0, 0, pKey2, nKey2, pRc); testScanCompare(pControl, pDb, 1, pKey1, nKey1, 0, 0, pRc); testScanCompare(pControl, pDb, 1, pKey1, nKey1, pKey2, nKey2, pRc); testFree(pKey1); } static void doDataTest2( const char *zSystem, /* Database system to test */ Datatest2 *p, /* Structure containing test parameters */ int *pRc /* OUT: Error code */ ){ |
︙ | ︙ | |||
389 390 391 392 393 394 395 | pKey1 = testMallocCopy(pKey1, nKey1); testDatasourceEntry(pData, i+2000000, &pKey2, &nKey2, 0, 0); testDeleteRange(pDb, pKey1, nKey1, pKey2, nKey2, &rc); testDeleteRange(pControl, pKey1, nKey1, pKey2, nKey2, &rc); testFree(pKey1); | > > > > | < | < | 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 | pKey1 = testMallocCopy(pKey1, nKey1); testDatasourceEntry(pData, i+2000000, &pKey2, &nKey2, 0, 0); testDeleteRange(pDb, pKey1, nKey1, pKey2, nKey2, &rc); testDeleteRange(pControl, pKey1, nKey1, pKey2, nKey2, &rc); testFree(pKey1); if( 0 && i==4 ){ extern int test_scan_debug; test_scan_debug = 1; } testCompareDb(pData, (p->nIter*p->nWrite), i, pControl, pDb, &rc); testReopen(&pDb, &rc); testCompareDb(pData, (p->nIter*p->nWrite), i, pControl, pDb, &rc); /* Update the progress dots... */ testCaseProgress(i, p->nIter, testCaseNDot(), &iDot); } testClose(&pDb); testClose(&pControl); |
︙ | ︙ | |||
424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 | void test_data_2( const char *zSystem, /* Database system name */ const char *zPattern, /* Run test cases that match this pattern */ int *pRc /* IN/OUT: Error code */ ){ Datatest2 aTest[] = { /* defn, nWrite, nIter */ { {DATA_RANDOM, 20,25, 100,200}, 200, 50 } }; int i; for(i=0; *pRc==LSM_OK && i<ArraySize(aTest); i++){ char *zName = getName2(zSystem, &aTest[i]); if( testCaseBegin(pRc, zPattern, "%s", zName) ){ doDataTest2(zSystem, &aTest[i], pRc); } testFree(zName); } } | > > > > | 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 | void test_data_2( const char *zSystem, /* Database system name */ const char *zPattern, /* Run test cases that match this pattern */ int *pRc /* IN/OUT: Error code */ ){ Datatest2 aTest[] = { /* defn, nWrite, nIter */ { {DATA_RANDOM, 20,25, 100,200}, 10, 50 }, { {DATA_RANDOM, 20,25, 100,200}, 200, 50 }, #if 0 { {DATA_RANDOM, 20,25, 100,200}, 200, 50 } #endif }; int i; for(i=0; *pRc==LSM_OK && i<ArraySize(aTest); i++){ char *zName = getName2(zSystem, &aTest[i]); if( testCaseBegin(pRc, zPattern, "%s", zName) ){ doDataTest2(zSystem, &aTest[i], pRc); } testFree(zName); } } |
Changes to lsm-test/lsmtest_main.c.
︙ | ︙ | |||
193 194 195 196 197 198 199 | void *pVal, int nVal ){ ScanResult *p = (ScanResult *)pCtx; u8 *aKey = (u8 *)pKey; u8 *aVal = (u8 *)pVal; int i; | | > > > | 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 | void *pVal, int nVal ){ ScanResult *p = (ScanResult *)pCtx; u8 *aKey = (u8 *)pKey; u8 *aVal = (u8 *)pVal; int i; if( test_scan_debug ){ printf("%.*s\n", nKey, (char *)pKey); fflush(stdout); } #if 0 if( test_scan_debug ) printf("%.20s\n", (char *)pVal); #endif #if 0 /* Check tdb_fetch() matches */ int rc = 0; |
︙ | ︙ |
Changes to src/lsmInt.h.
︙ | ︙ | |||
152 153 154 155 156 157 158 159 160 161 162 163 164 165 | ** Each entry stored in the LSM (or in-memory tree structure) has an ** associated mask of the following flags. */ #define LSM_START_DELETE 0x01 /* Start of open-ended delete range */ #define LSM_END_DELETE 0x02 /* End of open-ended delete range */ #define LSM_POINT_DELETE 0x04 /* Delete this key */ #define LSM_INSERT 0x08 /* Insert this key and value */ /* ** A string that can grow by appending. */ struct LsmString { lsm_env *pEnv; /* Run-time environment */ int n; /* Size of string. -1 indicates error */ | > > | 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 | ** Each entry stored in the LSM (or in-memory tree structure) has an ** associated mask of the following flags. */ #define LSM_START_DELETE 0x01 /* Start of open-ended delete range */ #define LSM_END_DELETE 0x02 /* End of open-ended delete range */ #define LSM_POINT_DELETE 0x04 /* Delete this key */ #define LSM_INSERT 0x08 /* Insert this key and value */ #define LSM_SEPARATOR 0x10 /* True if entry is separator key only */ #define LSM_SYSTEMKEY 0x20 /* True if entry is a system key (FREELIST) */ /* ** A string that can grow by appending. */ struct LsmString { lsm_env *pEnv; /* Run-time environment */ int n; /* Size of string. -1 indicates error */ |
︙ | ︙ | |||
384 385 386 387 388 389 390 391 392 393 394 395 396 397 | }; struct Merge { int nInput; /* Number of input runs being merged */ MergeInput *aInput; /* Array nInput entries in size */ MergeInput splitkey; /* Location in file of current splitkey */ int nSkip; /* Number of separators entries to skip */ int iOutputOff; /* Write offset on output page */ int bHierReadonly; /* True if b-tree heirarchies are read-only */ }; /* ** The first argument to this macro is a pointer to a Segment structure. ** Returns true if the structure instance indicates that the separators ** array is valid. | > | 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 | }; struct Merge { int nInput; /* Number of input runs being merged */ MergeInput *aInput; /* Array nInput entries in size */ MergeInput splitkey; /* Location in file of current splitkey */ int nSkip; /* Number of separators entries to skip */ int iOutputOff; /* Write offset on output page */ Pgno iCurrentPtr; /* Current pointer value */ int bHierReadonly; /* True if b-tree heirarchies are read-only */ }; /* ** The first argument to this macro is a pointer to a Segment structure. ** Returns true if the structure instance indicates that the separators ** array is valid. |
︙ | ︙ | |||
549 550 551 552 553 554 555 | void lsmTreeCursorDestroy(TreeCursor *); int lsmTreeCursorSeek(TreeCursor *pCsr, void *pKey, int nKey, int *pRes); int lsmTreeCursorNext(TreeCursor *pCsr); int lsmTreeCursorPrev(TreeCursor *pCsr); int lsmTreeCursorEnd(TreeCursor *pCsr, int bLast); void lsmTreeCursorReset(TreeCursor *pCsr); | | > > | 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 | void lsmTreeCursorDestroy(TreeCursor *); int lsmTreeCursorSeek(TreeCursor *pCsr, void *pKey, int nKey, int *pRes); int lsmTreeCursorNext(TreeCursor *pCsr); int lsmTreeCursorPrev(TreeCursor *pCsr); int lsmTreeCursorEnd(TreeCursor *pCsr, int bLast); void lsmTreeCursorReset(TreeCursor *pCsr); int lsmTreeCursorKey(TreeCursor *pCsr, int *pFlags, void **ppKey, int *pnKey); int lsmTreeCursorFlags(TreeCursor *pCsr); int lsmTreeCursorValue(TreeCursor *pCsr, void **ppVal, int *pnVal); int lsmTreeCursorValid(TreeCursor *pCsr); int lsmTreeCursorSave(TreeCursor *pCsr); void lsmFlagsToString(int flags, char *zFlags); /* ** Functions from file "mem.c". */ int lsmPoolNew(lsm_env *pEnv, Mempool **ppPool); void lsmPoolDestroy(lsm_env *pEnv, Mempool *pPool); void *lsmPoolMalloc(lsm_env *pEnv, Mempool *pPool, int nByte); |
︙ | ︙ |
Changes to src/lsm_ckpt.c.
︙ | ︙ | |||
60 61 62 63 64 65 66 67 68 69 70 71 72 73 | ** 4. If nRight>0, The number of segments involved in the merge ** 5. if nRight>0, Current nSkip value (see Merge structure defn.), ** 6. For each segment in the merge: ** 5a. Page number of next cell to read during merge ** 5b. Cell number of next cell to read during merge ** 7. Page containing current split-key. ** 8. Cell within page containing current split-key. ** ** The freelist. ** ** 1. Number of free-list entries stored in checkpoint header. ** 2. For each entry: ** 2a. Block number of free block. ** 2b. MSW of associated checkpoint id. | > | 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | ** 4. If nRight>0, The number of segments involved in the merge ** 5. if nRight>0, Current nSkip value (see Merge structure defn.), ** 6. For each segment in the merge: ** 5a. Page number of next cell to read during merge ** 5b. Cell number of next cell to read during merge ** 7. Page containing current split-key. ** 8. Cell within page containing current split-key. ** 9. Current pointer value. ** ** The freelist. ** ** 1. Number of free-list entries stored in checkpoint header. ** 2. For each entry: ** 2a. Block number of free block. ** 2b. MSW of associated checkpoint id. |
︙ | ︙ | |||
308 309 310 311 312 313 314 315 316 317 318 319 320 321 | ckptSetValue(p, iOut++, pMerge->nSkip, pRc); for(i=0; i<pMerge->nInput; i++){ ckptSetValue(p, iOut++, pMerge->aInput[i].iPg, pRc); ckptSetValue(p, iOut++, pMerge->aInput[i].iCell, pRc); } ckptSetValue(p, iOut++, pMerge->splitkey.iPg, pRc); ckptSetValue(p, iOut++, pMerge->splitkey.iCell, pRc); } *piOut = iOut; } /* ** Populate the log offset fields of the checkpoint buffer. 4 values. | > | 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 | ckptSetValue(p, iOut++, pMerge->nSkip, pRc); for(i=0; i<pMerge->nInput; i++){ ckptSetValue(p, iOut++, pMerge->aInput[i].iPg, pRc); ckptSetValue(p, iOut++, pMerge->aInput[i].iCell, pRc); } ckptSetValue(p, iOut++, pMerge->splitkey.iPg, pRc); ckptSetValue(p, iOut++, pMerge->splitkey.iCell, pRc); ckptSetValue(p, iOut++, pMerge->iCurrentPtr, pRc); } *piOut = iOut; } /* ** Populate the log offset fields of the checkpoint buffer. 4 values. |
︙ | ︙ | |||
497 498 499 500 501 502 503 504 505 506 507 508 509 510 | pMerge->nSkip = (int)aInt[iIn++]; for(i=0; i<nInput; i++){ pMerge->aInput[i].iPg = (Pgno)aInt[iIn++]; pMerge->aInput[i].iCell = (int)aInt[iIn++]; } pMerge->splitkey.iPg = (Pgno)aInt[iIn++]; pMerge->splitkey.iCell = (int)aInt[iIn++]; /* Set *piIn and return LSM_OK. */ *piIn = iIn; return LSM_OK; } | > | 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 | pMerge->nSkip = (int)aInt[iIn++]; for(i=0; i<nInput; i++){ pMerge->aInput[i].iPg = (Pgno)aInt[iIn++]; pMerge->aInput[i].iCell = (int)aInt[iIn++]; } pMerge->splitkey.iPg = (Pgno)aInt[iIn++]; pMerge->splitkey.iCell = (int)aInt[iIn++]; pMerge->iCurrentPtr = (int)aInt[iIn++]; /* Set *piIn and return LSM_OK. */ *piIn = iIn; return LSM_OK; } |
︙ | ︙ |
Changes to src/lsm_sorted.c.
︙ | ︙ | |||
38 39 40 41 42 43 44 | ** (N==0). And on most pages the first record that starts on the page will ** not start at byte offset 0. For example: ** ** aaaaa bbbbb ccc <footer> cc eeeee fffff g <footer> gggg.... ** ** RECORD FORMAT: ** | < < < | > > | > | | > < | | | | | | | < < < < < < < < < < < < < < < < < < < < < < < < < < < < < | | > | | > | 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 | ** (N==0). And on most pages the first record that starts on the page will ** not start at byte offset 0. For example: ** ** aaaaa bbbbb ccc <footer> cc eeeee fffff g <footer> gggg.... ** ** RECORD FORMAT: ** ** The first byte of the record is a flags byte. It is a combination ** of the following flags (defined in lsmInt.h): ** ** LSM_START_DELETE ** LSM_END_DELETE ** LSM_POINT_DELETE ** LSM_INSERT ** LSM_SEPARATOR ** LSM_SYSTEMKEY ** ** Immediately following the type byte is a pointer to the smallest key ** in the next file that is larger than the key in the current record. The ** pointer is encoded as a varint. When added to the 32-bit page number ** stored in the footer, it is the page number of the page that contains the ** smallest key in the next sorted file that is larger than this key. ** ** Next is the number of bytes in the key, encoded as a varint. ** ** If the LSM_INSERT flag is set, the number of bytes in the value, as ** a varint, is next. ** ** Finally, the blob of data containing the key, and for LSM_INSERT ** records, the value as well. */ #ifndef _LSM_INT_H # include "lsmInt.h" #endif #include "sqlite4.h" /* only for sqlite4_snprintf() */ /* ** Macros to help decode record types. */ #define rtTopic(eType) ((eType) & LSM_SYSTEMKEY) #define rtIsDelete(eType) (((eType) & 0x0F)==LSM_POINT_DELETE) #define rtIsSeparator(eType) (((eType) & LSM_SEPARATOR)!=0) #define rtIsWrite(eType) (((eType) & LSM_INSERT)!=0) #define rtIsSystem(eType) (((eType) & LSM_SYSTEMKEY)!=0) /* ** The following macros are used to access a page footer. */ #define SEGMENT_NRECORD_OFFSET(pgsz) ((pgsz) - 2) #define SEGMENT_FLAGS_OFFSET(pgsz) ((pgsz) - 2 - 2) #define SEGMENT_POINTER_OFFSET(pgsz) ((pgsz) - 2 - 2 - 4) |
︙ | ︙ | |||
230 231 232 233 234 235 236 237 238 239 240 241 242 243 | /* Comparison results */ int nTree; /* Size of aTree[] array */ int *aTree; /* Array of comparison results */ /* Used by cursors flushing the in-memory tree only */ int *pnOvfl; /* Number of free-list entries to store */ void *pSystemVal; /* Pointer to buffer to free */ }; #define CURSOR_DATA_TREE0 0 /* Current tree cursor */ #define CURSOR_DATA_TREE1 1 /* The "old" tree, if any */ #define CURSOR_DATA_SYSTEM 2 #define CURSOR_DATA_SEGMENT 3 | > > > | 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 | /* Comparison results */ int nTree; /* Size of aTree[] array */ int *aTree; /* Array of comparison results */ /* Used by cursors flushing the in-memory tree only */ int *pnOvfl; /* Number of free-list entries to store */ void *pSystemVal; /* Pointer to buffer to free */ /* Used by worker cursors only */ Pgno *pPrevMergePtr; }; #define CURSOR_DATA_TREE0 0 /* Current tree cursor */ #define CURSOR_DATA_TREE1 1 /* The "old" tree, if any */ #define CURSOR_DATA_SYSTEM 2 #define CURSOR_DATA_SEGMENT 3 |
︙ | ︙ | |||
610 611 612 613 614 615 616 | } if( iPg<0 || iCell<0 ) return LSM_CORRUPT_BKPT; rc = pageGetBtreeKey( pCsr->aPg[iPg].pPage, iCell, &dummy, &pCsr->eType, &pCsr->pKey, &pCsr->nKey, &pCsr->blob ); | | | 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 | } if( iPg<0 || iCell<0 ) return LSM_CORRUPT_BKPT; rc = pageGetBtreeKey( pCsr->aPg[iPg].pPage, iCell, &dummy, &pCsr->eType, &pCsr->pKey, &pCsr->nKey, &pCsr->blob ); pCsr->eType |= LSM_SEPARATOR; } return rc; } static int btreeCursorPtr(u8 *aData, int nData, int iCell){ int nCell; |
︙ | ︙ | |||
918 919 920 921 922 923 924 | if( pCsr->aPg[i].iCell>0 ) break; } assert( i>=0 ); rc = pageGetBtreeKey( pCsr->aPg[i].pPage, pCsr->aPg[i].iCell-1, &dummy, &pCsr->eType, &pCsr->pKey, &pCsr->nKey, &pCsr->blob ); | | | 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 | if( pCsr->aPg[i].iCell>0 ) break; } assert( i>=0 ); rc = pageGetBtreeKey( pCsr->aPg[i].pPage, pCsr->aPg[i].iCell-1, &dummy, &pCsr->eType, &pCsr->pKey, &pCsr->nKey, &pCsr->blob ); pCsr->eType |= LSM_SEPARATOR; }else{ rc = btreeCursorLoadKey(pCsr); } } } return rc; |
︙ | ︙ | |||
1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 | int rc = LSM_OK; int iMin; int iMax; int iPtrOut = 0; const int iTopic = 0; /* If the OVERSIZED flag is set, then there is no pointer in the ** upper level to the next page in the segment that contains at least ** one key. So compare the largest key on the current page with the ** key being sought (pKey/nKey). If (pKey/nKey) is larger, advance ** to the next page in the segment that contains at least one key. */ while( rc==LSM_OK && (pPtr->flags & PGFTR_SKIP_NEXT_FLAG) ){ | > > > > > > > | 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 | int rc = LSM_OK; int iMin; int iMax; int iPtrOut = 0; const int iTopic = 0; #if 0 static int nCall = 0; nCall++; printf("in call %d\n", nCall); fflush(stdout); #endif /* If the OVERSIZED flag is set, then there is no pointer in the ** upper level to the next page in the segment that contains at least ** one key. So compare the largest key on the current page with the ** key being sought (pKey/nKey). If (pKey/nKey) is larger, advance ** to the next page in the segment that contains at least one key. */ while( rc==LSM_OK && (pPtr->flags & PGFTR_SKIP_NEXT_FLAG) ){ |
︙ | ︙ | |||
1631 1632 1633 1634 1635 1636 1637 | case CURSOR_DATA_TREE0: case CURSOR_DATA_TREE1: { TreeCursor *pTreeCsr = pCsr->apTreeCsr[iKey-CURSOR_DATA_TREE0]; if( lsmTreeCursorValid(pTreeCsr) ){ int nVal; void *pVal; | | < | | 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 | case CURSOR_DATA_TREE0: case CURSOR_DATA_TREE1: { TreeCursor *pTreeCsr = pCsr->apTreeCsr[iKey-CURSOR_DATA_TREE0]; if( lsmTreeCursorValid(pTreeCsr) ){ int nVal; void *pVal; lsmTreeCursorKey(pTreeCsr, &eType, &pKey, &nKey); lsmTreeCursorValue(pTreeCsr, &pVal, &nVal); } break; } case CURSOR_DATA_SYSTEM: if( pCsr->flags & CURSOR_AT_FREELIST ){ pKey = (void *)"FREELIST"; nKey = 8; eType = LSM_SYSTEMKEY | LSM_INSERT; } break; default: { int iPtr = iKey - CURSOR_DATA_SEGMENT; assert( iPtr>=0 ); if( iPtr==pCsr->nPtr ){ |
︙ | ︙ | |||
1679 1680 1681 1682 1683 1684 1685 | static void multiCursorDoCompare(MultiCursor *pCsr, int iOut, int bReverse){ int i1; int i2; int iRes; void *pKey1; int nKey1; int eType1; void *pKey2; int nKey2; int eType2; | < | > > > | > > > > > > > > > | > > > > > < > | 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 | static void multiCursorDoCompare(MultiCursor *pCsr, int iOut, int bReverse){ int i1; int i2; int iRes; void *pKey1; int nKey1; int eType1; void *pKey2; int nKey2; int eType2; const int mul = (bReverse ? -1 : 1); assert( pCsr->aTree && iOut<pCsr->nTree ); if( iOut>=(pCsr->nTree/2) ){ i1 = (iOut - pCsr->nTree/2) * 2; i2 = i1 + 1; }else{ i1 = pCsr->aTree[iOut*2]; i2 = pCsr->aTree[iOut*2+1]; } multiCursorGetKey(pCsr, i1, &eType1, &pKey1, &nKey1); multiCursorGetKey(pCsr, i2, &eType2, &pKey2, &nKey2); if( pKey1==0 ){ iRes = i2; }else if( pKey2==0 ){ iRes = i1; }else{ int res; /* Compare the keys, including the system flag. */ res = sortedKeyCompare(pCsr->pDb->xCmp, rtTopic(eType1), pKey1, nKey1, rtTopic(eType2), pKey2, nKey2 ); /* If a key has the LSM_START_DELETE flag set, but not the LSM_INSERT or ** LSM_POINT_DELETE flags, it is considered a delta larger. This prevents ** the beginning of an open-ended set from masking a database entry or ** delete at a lower level. */ if( res==0 ){ const int insdel = LSM_POINT_DELETE|LSM_INSERT; int iDel1 = 0; int iDel2 = 0; if( LSM_START_DELETE==(eType1 & (LSM_START_DELETE|insdel)) ) iDel1 = +1; if( LSM_END_DELETE ==(eType1 & (LSM_END_DELETE |insdel)) ) iDel1 = -1; if( LSM_START_DELETE==(eType2 & (LSM_START_DELETE|insdel)) ) iDel2 = +1; if( LSM_END_DELETE ==(eType2 & (LSM_END_DELETE |insdel)) ) iDel2 = -1; res = (iDel1 - iDel2); } res = res * mul; if( res==0 ){ iRes = (rtIsSeparator(eType1) ? i2 : i1); }else if( res<0 ){ iRes = i1; }else{ iRes = i2; } |
︙ | ︙ | |||
2077 2078 2079 2080 2081 2082 2083 | rc = multiCursorAddAll(pCsr, pDb->pWorker); pCsr->flags |= CURSOR_IGNORE_DELETE; } if( rc==LSM_OK ){ rc = lsmMCursorLast(pCsr); if( rc==LSM_OK | | | 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085 2086 2087 2088 2089 | rc = multiCursorAddAll(pCsr, pDb->pWorker); pCsr->flags |= CURSOR_IGNORE_DELETE; } if( rc==LSM_OK ){ rc = lsmMCursorLast(pCsr); if( rc==LSM_OK && rtIsWrite(pCsr->eType) && rtIsSystem(pCsr->eType) && pCsr->key.nData==8 && 0==memcmp(pCsr->key.pData, "FREELIST", 8) ){ void *pVal; int nVal; /* Value read from database */ rc = lsmMCursorValue(pCsr, &pVal, &nVal); if( rc==LSM_OK ){ *ppVal = lsmMallocRc(pDb->pEnv, nVal, &rc); |
︙ | ︙ | |||
2124 2125 2126 2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 | if( *pRc==LSM_OK ){ void *pKey; int nKey; multiCursorGetKey(pCsr, pCsr->aTree[1], &pCsr->eType, &pKey, &nKey); *pRc = sortedBlobSet(pCsr->pDb->pEnv, &pCsr->key, pKey, nKey); } } static int multiCursorEnd(MultiCursor *pCsr, int bLast){ int rc = LSM_OK; int i; pCsr->flags &= ~(CURSOR_NEXT_OK | CURSOR_PREV_OK); if( pCsr->apTreeCsr[0] ){ rc = lsmTreeCursorEnd(pCsr->apTreeCsr[0], bLast); } if( rc==LSM_OK && pCsr->apTreeCsr[1] ){ rc = lsmTreeCursorEnd(pCsr->apTreeCsr[1], bLast); } | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 | if( *pRc==LSM_OK ){ void *pKey; int nKey; multiCursorGetKey(pCsr, pCsr->aTree[1], &pCsr->eType, &pKey, &nKey); *pRc = sortedBlobSet(pCsr->pDb->pEnv, &pCsr->key, pKey, nKey); } } static int mcursorLocationOk(MultiCursor *pCsr, int bDeleteOk){ int eType = pCsr->eType; int iKey; int i; int rdmask = 0; /* assert( pCsr->flags & (CURSOR_NEXT_OK|CURSOR_PREV_OK) ); */ if( pCsr->flags & CURSOR_NEXT_OK ){ rdmask = LSM_END_DELETE; }else if( pCsr->flags & CURSOR_PREV_OK ){ rdmask = LSM_START_DELETE; } if( (pCsr->flags & CURSOR_IGNORE_DELETE) && bDeleteOk==0 ){ if( (eType & LSM_INSERT)==0 ) return 0; } if( (pCsr->flags & CURSOR_IGNORE_SYSTEM) && rtTopic(eType)!=0 ){ return 0; } /* Check if this key has already been deleted by a range-delete */ iKey = pCsr->aTree[1]; if( (iKey>0 && (rdmask & lsmTreeCursorFlags(pCsr->apTreeCsr[0]))) || (iKey>1 && (rdmask & lsmTreeCursorFlags(pCsr->apTreeCsr[1]))) ){ return 0; } for(i=CURSOR_DATA_SEGMENT; i<iKey; i++){ int iPtr = i-CURSOR_DATA_SEGMENT; if( pCsr->aPtr[iPtr].pPg && (pCsr->aPtr[iPtr].eType & rdmask) ){ return 0; } } return 1; } static int multiCursorEnd(MultiCursor *pCsr, int bLast){ int rc = LSM_OK; int i; pCsr->flags &= ~(CURSOR_NEXT_OK | CURSOR_PREV_OK); pCsr->flags |= (bLast ? CURSOR_PREV_OK : CURSOR_NEXT_OK); if( pCsr->apTreeCsr[0] ){ rc = lsmTreeCursorEnd(pCsr->apTreeCsr[0], bLast); } if( rc==LSM_OK && pCsr->apTreeCsr[1] ){ rc = lsmTreeCursorEnd(pCsr->apTreeCsr[1], bLast); } |
︙ | ︙ | |||
2173 2174 2175 2176 2177 2178 2179 | if( rc==LSM_OK ){ rc = multiCursorAllocTree(pCsr); } if( rc==LSM_OK ){ for(i=pCsr->nTree-1; i>0; i--){ multiCursorDoCompare(pCsr, i, bLast); } | < | < < < | 2210 2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224 2225 2226 2227 | if( rc==LSM_OK ){ rc = multiCursorAllocTree(pCsr); } if( rc==LSM_OK ){ for(i=pCsr->nTree-1; i>0; i--){ multiCursorDoCompare(pCsr, i, bLast); } } multiCursorCacheKey(pCsr, &rc); if( rc==LSM_OK && mcursorLocationOk(pCsr, 0)==0 ){ if( bLast ){ rc = lsmMCursorPrev(pCsr); }else{ rc = lsmMCursorNext(pCsr); } } |
︙ | ︙ | |||
2285 2286 2287 2288 2289 2290 2291 | } break; } } } | < < < < < < < < < < < < | 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 | } break; } } } /* ** Seek the cursor. */ int lsmMCursorSeek(MultiCursor *pCsr, void *pKey, int nKey, int eSeek){ int eESeek = eSeek; /* Effective eSeek parameter */ int rc = LSM_OK; int iPtr = 0; |
︙ | ︙ | |||
2395 2396 2397 2398 2399 2400 2401 | int res = rtTopic(eNewType) - rtTopic(pCsr->eType); if( res==0 ){ res = pCsr->pDb->xCmp(pNew, nNew, pCsr->key.pData, pCsr->key.nData); } if( (bReverse==0 && res<=0) || (bReverse!=0 && res>=0) ){ return 0; } | | < | | | | | | | | | | > > > > > > > > > > > > > > > > > < | 2416 2417 2418 2419 2420 2421 2422 2423 2424 2425 2426 2427 2428 2429 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447 2448 2449 2450 2451 2452 2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 2469 2470 2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 | int res = rtTopic(eNewType) - rtTopic(pCsr->eType); if( res==0 ){ res = pCsr->pDb->xCmp(pNew, nNew, pCsr->key.pData, pCsr->key.nData); } if( (bReverse==0 && res<=0) || (bReverse!=0 && res>=0) ){ return 0; } multiCursorCacheKey(pCsr, pRc); assert( pCsr->eType==eNewType ); /* If this cursor is configured to skip deleted keys, and the current ** cursor points to a SORTED_DELETE entry, then the cursor has not been ** successfully advanced. ** ** Similarly, if the cursor is configured to skip system keys and the ** current cursor points to a system key, it has not yet been advanced. */ if( *pRc==LSM_OK && 0==mcursorLocationOk(pCsr, 0) ) return 0; } return 1; } static int multiCursorAdvance(MultiCursor *pCsr, int bReverse){ int rc = LSM_OK; /* Return Code */ if( lsmMCursorValid(pCsr) ){ do { int iKey = pCsr->aTree[1]; /* If this multi-cursor is advancing forwards, and the sub-cursor ** being advanced is the one that separator keys may be being read ** from, record the current absolute pointer value. */ if( pCsr->pPrevMergePtr && iKey>=CURSOR_DATA_SEGMENT && iKey==(CURSOR_DATA_SEGMENT+pCsr->nPtr-(!pCsr->pBtCsr)) ){ if( iKey==(CURSOR_DATA_SEGMENT+pCsr->nPtr) ){ *pCsr->pPrevMergePtr = pCsr->pBtCsr->iPtr; }else{ SegmentPtr *pPtr = &pCsr->aPtr[iKey-CURSOR_DATA_SEGMENT]; *pCsr->pPrevMergePtr = pPtr->iPtr+pPtr->iPgPtr; } } if( iKey==CURSOR_DATA_TREE0 || iKey==CURSOR_DATA_TREE1 ){ TreeCursor *pTreeCsr = pCsr->apTreeCsr[iKey-CURSOR_DATA_TREE0]; if( bReverse ){ rc = lsmTreeCursorPrev(pTreeCsr); }else{ rc = lsmTreeCursorNext(pTreeCsr); } }else if( iKey==CURSOR_DATA_SYSTEM ){ assert( pCsr->flags & CURSOR_AT_FREELIST ); assert( pCsr->flags & CURSOR_NEW_SYSTEM ); assert( bReverse==0 ); pCsr->flags &= ~CURSOR_AT_FREELIST; }else if( iKey==(CURSOR_DATA_SEGMENT+pCsr->nPtr) ){ assert( bReverse==0 && pCsr->pBtCsr ); rc = btreeCursorNext(pCsr->pBtCsr); }else{ rc = segmentCursorAdvance(pCsr, iKey-CURSOR_DATA_SEGMENT, bReverse); } if( rc==LSM_OK ){ int i; for(i=(iKey+pCsr->nTree)/2; i>0; i=i/2){ multiCursorDoCompare(pCsr, i, bReverse); } } }while( mcursorAdvanceOk(pCsr, bReverse, &rc)==0 ); |
︙ | ︙ | |||
2461 2462 2463 2464 2465 2466 2467 | } int lsmMCursorKey(MultiCursor *pCsr, void **ppKey, int *pnKey){ int iKey = pCsr->aTree[1]; if( iKey==CURSOR_DATA_TREE0 || iKey==CURSOR_DATA_TREE1 ){ TreeCursor *pTreeCsr = pCsr->apTreeCsr[iKey-CURSOR_DATA_TREE0]; | | | 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510 2511 | } int lsmMCursorKey(MultiCursor *pCsr, void **ppKey, int *pnKey){ int iKey = pCsr->aTree[1]; if( iKey==CURSOR_DATA_TREE0 || iKey==CURSOR_DATA_TREE1 ){ TreeCursor *pTreeCsr = pCsr->apTreeCsr[iKey-CURSOR_DATA_TREE0]; lsmTreeCursorKey(pTreeCsr, 0, ppKey, pnKey); }else{ int nKey; #ifndef NDEBUG void *pKey; int eType; multiCursorGetKey(pCsr, iKey, &eType, &pKey, &nKey); |
︙ | ︙ | |||
2491 2492 2493 2494 2495 2496 2497 | int lsmMCursorValue(MultiCursor *pCsr, void **ppVal, int *pnVal){ void *pVal; int nVal; int rc; assert( pCsr->aTree ); | | | 2527 2528 2529 2530 2531 2532 2533 2534 2535 2536 2537 2538 2539 2540 2541 | int lsmMCursorValue(MultiCursor *pCsr, void **ppVal, int *pnVal){ void *pVal; int nVal; int rc; assert( pCsr->aTree ); assert( mcursorLocationOk(pCsr, (pCsr->flags & CURSOR_IGNORE_DELETE)) ); rc = multiCursorGetVal(pCsr, pCsr->aTree[1], &pVal, &nVal); if( pVal && rc==LSM_OK ){ rc = sortedBlobSet(pCsr->pDb->pEnv, &pCsr->val, pVal, nVal); pVal = pCsr->val.pData; } |
︙ | ︙ | |||
2530 2531 2532 2533 2534 2535 2536 | int nKey; int eType; nRec = lsmGetU16(&aData[SEGMENT_NRECORD_OFFSET(nData)]); iOff = lsmGetU16(&aData[SEGMENT_CELLPTR_OFFSET(nData, nRec-1)]); eType = aData[iOff++]; assert( eType==0 | | | | 2566 2567 2568 2569 2570 2571 2572 2573 2574 2575 2576 2577 2578 2579 2580 2581 | int nKey; int eType; nRec = lsmGetU16(&aData[SEGMENT_NRECORD_OFFSET(nData)]); iOff = lsmGetU16(&aData[SEGMENT_CELLPTR_OFFSET(nData, nRec-1)]); eType = aData[iOff++]; assert( eType==0 || eType==(LSM_SYSTEMKEY|LSM_SEPARATOR) || eType==(LSM_SEPARATOR) ); iOff += lsmVarintGet32(&aData[iOff], &nKey); iOff += lsmVarintGet32(&aData[iOff], &nKey); return iOff + (eType ? nKey : 0); } |
︙ | ︙ | |||
2856 2857 2858 2859 2860 2861 2862 | lsmPutU16(&aData[SEGMENT_NRECORD_OFFSET(nData)], nRec+1); if( bIndirect ){ aData[iOff++] = 0x00; iOff += lsmVarintPut32(&aData[iOff], iPtr); iOff += lsmVarintPut32(&aData[iOff], iKeyPg); }else{ | | | 2892 2893 2894 2895 2896 2897 2898 2899 2900 2901 2902 2903 2904 2905 2906 | lsmPutU16(&aData[SEGMENT_NRECORD_OFFSET(nData)], nRec+1); if( bIndirect ){ aData[iOff++] = 0x00; iOff += lsmVarintPut32(&aData[iOff], iPtr); iOff += lsmVarintPut32(&aData[iOff], iKeyPg); }else{ aData[iOff++] = (u8)(iTopic | LSM_SEPARATOR); iOff += lsmVarintPut32(&aData[iOff], iPtr); iOff += lsmVarintPut32(&aData[iOff], nKey); memcpy(&aData[iOff], pKey, nKey); } if( iLevel>0 ){ int iRight = lsmFsPageNumber(p->apHier[iLevel-1]); |
︙ | ︙ | |||
3004 3005 3006 3007 3008 3009 3010 | pPg = pMW->pPage; aData = fsPageData(pPg, &nData); nRec = pageGetNRec(aData, nData); iFPtr = pageGetPtr(aData, nData); /* If iPtr is 0, set it to the same value as the absolute pointer ** stored as part of the previous record. */ | | | 3040 3041 3042 3043 3044 3045 3046 3047 3048 3049 3050 3051 3052 3053 3054 | pPg = pMW->pPage; aData = fsPageData(pPg, &nData); nRec = pageGetNRec(aData, nData); iFPtr = pageGetPtr(aData, nData); /* If iPtr is 0, set it to the same value as the absolute pointer ** stored as part of the previous record. */ if( 0 && iPtr==0 ){ iPtr = iFPtr; if( nRec ) iPtr += pageGetRecordPtr(aData, nData, nRec-1); } /* Calculate the relative pointer value to write to this record */ iRPtr = iPtr - iFPtr; /* assert( iRPtr>=0 ); */ |
︙ | ︙ | |||
3036 3037 3038 3039 3040 3041 3042 3043 3044 3045 3046 3047 3048 3049 3050 3051 | nHdr = 1 + lsmVarintLen32(iRPtr) + lsmVarintLen32(nKey); if( rtIsWrite(eType) ) nHdr += lsmVarintLen32(nVal); /* If the entire header will not fit on page pPg, or if page pPg is ** marked read-only, advance to the next page of the output run. */ iOff = pMerge->iOutputOff; if( iOff<0 || iOff+nHdr > SEGMENT_EOF(nData, nRec+1) ){ iFPtr = iFPtr + (nRec ? pageGetRecordPtr(aData, nData, nRec-1) : 0); iRPtr = iPtr - iFPtr; iOff = 0; nRec = 0; rc = mergeWorkerNextPage(pMW, iFPtr); pPg = pMW->pPage; } } | > > > > > | 3072 3073 3074 3075 3076 3077 3078 3079 3080 3081 3082 3083 3084 3085 3086 3087 3088 3089 3090 3091 3092 | nHdr = 1 + lsmVarintLen32(iRPtr) + lsmVarintLen32(nKey); if( rtIsWrite(eType) ) nHdr += lsmVarintLen32(nVal); /* If the entire header will not fit on page pPg, or if page pPg is ** marked read-only, advance to the next page of the output run. */ iOff = pMerge->iOutputOff; if( iOff<0 || iOff+nHdr > SEGMENT_EOF(nData, nRec+1) ){ #if 0 iFPtr = iFPtr + (nRec ? pageGetRecordPtr(aData, nData, nRec-1) : 0); iRPtr = iPtr - iFPtr; #endif iFPtr = *pCsr->pPrevMergePtr; iRPtr = iPtr - iFPtr; iOff = 0; nRec = 0; rc = mergeWorkerNextPage(pMW, iFPtr); pPg = pMW->pPage; } } |
︙ | ︙ | |||
3211 3212 3213 3214 3215 3216 3217 3218 3219 3220 3221 3222 3223 3224 3225 3226 3227 3228 3229 | iFPtr = pageGetPtr(aData, nData); lsmFsPageRelease(pPg); } } if( rc==LSM_OK ){ rc = mergeWorkerNextPage(pMW, iFPtr); } return rc; } static int mergeWorkerStep(MergeWorker *pMW){ lsm_db *pDb = pMW->pDb; /* Database handle */ MultiCursor *pCsr; /* Cursor to read input data from */ int rc = LSM_OK; /* Return code */ int eType; /* SORTED_SEPARATOR, WRITE or DELETE */ void *pKey; int nKey; /* Key */ Segment *pSeg; /* Output segment */ | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | > < > > > | | | | | | | | | | | | | | | | | | | | > | 3252 3253 3254 3255 3256 3257 3258 3259 3260 3261 3262 3263 3264 3265 3266 3267 3268 3269 3270 3271 3272 3273 3274 3275 3276 3277 3278 3279 3280 3281 3282 3283 3284 3285 3286 3287 3288 3289 3290 3291 3292 3293 3294 3295 3296 3297 3298 3299 3300 3301 3302 3303 3304 3305 3306 3307 3308 3309 3310 3311 3312 3313 3314 3315 3316 3317 3318 3319 3320 3321 3322 3323 3324 3325 3326 3327 3328 3329 3330 3331 3332 3333 3334 3335 3336 3337 3338 3339 3340 3341 3342 3343 3344 3345 3346 3347 3348 3349 3350 3351 3352 3353 3354 3355 3356 3357 3358 3359 3360 3361 3362 3363 3364 3365 3366 3367 3368 3369 3370 3371 3372 3373 3374 3375 3376 3377 3378 | iFPtr = pageGetPtr(aData, nData); lsmFsPageRelease(pPg); } } if( rc==LSM_OK ){ rc = mergeWorkerNextPage(pMW, iFPtr); if( pCsr->pPrevMergePtr ) *pCsr->pPrevMergePtr = iFPtr; } return rc; } /* ** The cursor passed as the first argument is being used as the input for ** a merge operation. When this function is called, *piFlags contains the ** database entry flags for the current entry. The entry about to be written ** to the output. ** */ static void mergeRangeDeletes(MultiCursor *pCsr, int *piFlags){ int f = *piFlags; int iKey = pCsr->aTree[1]; int i; if( pCsr->flags & CURSOR_IGNORE_DELETE ){ /* The ignore-delete flag is set when the output of the merge will form ** the oldest level in the database. In this case there is no point in ** retaining any range-delete flags. */ assert( (f & LSM_POINT_DELETE)==0 ); f &= ~(LSM_START_DELETE|LSM_END_DELETE); }else{ if( iKey==0 ){ int btreeflags = lsmTreeCursorFlags(pCsr->apTreeCsr[1]); if( btreeflags & LSM_END_DELETE ){ f |= (LSM_START_DELETE|LSM_END_DELETE); } } for(i=LSM_MAX(0, iKey+1-CURSOR_DATA_SEGMENT); i<pCsr->nPtr; i++){ if( pCsr->aPtr[i].eType & LSM_END_DELETE ){ f |= (LSM_START_DELETE|LSM_END_DELETE); } } if( (f & LSM_START_DELETE) && (f & LSM_END_DELETE) && (f & LSM_INSERT)==0 ){ f = 0; } } *piFlags = f; } static int mergeWorkerStep(MergeWorker *pMW){ lsm_db *pDb = pMW->pDb; /* Database handle */ MultiCursor *pCsr; /* Cursor to read input data from */ int rc = LSM_OK; /* Return code */ int eType; /* SORTED_SEPARATOR, WRITE or DELETE */ void *pKey; int nKey; /* Key */ Segment *pSeg; /* Output segment */ Pgno iPtr; pCsr = pMW->pCsr; pSeg = &pMW->pLevel->lhs; /* Pull the next record out of the source cursor. */ lsmMCursorKey(pCsr, &pKey, &nKey); eType = pCsr->eType; /* Figure out if the output record may have a different pointer value ** than the previous. This is the case if the current key is identical to ** a key that appears in the lowest level run being merged. If so, set ** iPtr to the absolute pointer value. If not, leave iPtr set to zero, ** indicating that the output pointer value should be a copy of the pointer ** value written with the previous key. */ iPtr = (pCsr->pPrevMergePtr ? *pCsr->pPrevMergePtr : 0); if( pCsr->pBtCsr ){ BtreeCursor *pBtCsr = pCsr->pBtCsr; if( pBtCsr->pKey ){ int res = rtTopic(pBtCsr->eType) - rtTopic(eType); if( res==0 ) res = pDb->xCmp(pBtCsr->pKey, pBtCsr->nKey, pKey, nKey); if( 0==res ) iPtr = pBtCsr->iPtr; assert( res>=0 ); } }else if( pCsr->nPtr ){ SegmentPtr *pPtr = &pCsr->aPtr[pCsr->nPtr-1]; if( pPtr->pPg && 0==pDb->xCmp(pPtr->pKey, pPtr->nKey, pKey, nKey) ){ iPtr = pPtr->iPtr+pPtr->iPgPtr; } } mergeRangeDeletes(pCsr, &eType); if( eType!=0 ){ if( pMW->aGobble ){ int iGobble = pCsr->aTree[1] - CURSOR_DATA_SEGMENT; if( iGobble<pCsr->nPtr ){ SegmentPtr *pGobble = &pCsr->aPtr[iGobble]; if( (pGobble->flags & PGFTR_SKIP_THIS_FLAG)==0 ){ pMW->aGobble[iGobble] = lsmFsPageNumber(pGobble->pPg); } } } /* If this is a separator key and we know that the output pointer has not ** changed, there is no point in writing an output record. Otherwise, ** proceed. */ if( rtIsSeparator(eType)==0 || iPtr!=0 ){ int iSPtr = 0; /* Separators require a pointer here */ if( pMW->pPage==0 ){ rc = mergeWorkerFirstPage(pMW); } /* Write the record into the main run. */ if( rc==LSM_OK ){ rc = mergeWorkerWrite(pMW, eType, pKey, nKey, pCsr, iPtr, &iSPtr); } } } /* Advance the cursor to the next input record (assuming one exists). */ assert( lsmMCursorValid(pMW->pCsr) ); if( rc==LSM_OK ) rc = lsmMCursorNext(pMW->pCsr); |
︙ | ︙ | |||
3372 3373 3374 3375 3376 3377 3378 3379 3380 3381 3382 3383 3384 3385 3386 3387 3388 3389 3390 3391 3392 3393 3394 3395 | iLeftPtr = pNext->lhs.iFirst; } } if( rc!=LSM_OK ){ lsmMCursorClose(pCsr); }else{ Merge merge; /* Merge object used to create new level */ MergeWorker mergeworker; /* MergeWorker object for the same purpose */ memset(&merge, 0, sizeof(Merge)); memset(&mergeworker, 0, sizeof(MergeWorker)); pNew->pMerge = &merge; mergeworker.pDb = pDb; mergeworker.pLevel = pNew; mergeworker.pCsr = pCsr; /* Mark the separators array for the new level as a "phantom". */ mergeworker.bFlush = 1; /* Allocate the first page of the output segment. */ rc = mergeWorkerNextPage(&mergeworker, iLeftPtr); | > > | 3458 3459 3460 3461 3462 3463 3464 3465 3466 3467 3468 3469 3470 3471 3472 3473 3474 3475 3476 3477 3478 3479 3480 3481 3482 3483 | iLeftPtr = pNext->lhs.iFirst; } } if( rc!=LSM_OK ){ lsmMCursorClose(pCsr); }else{ Pgno iCurrentPtr = 0; Merge merge; /* Merge object used to create new level */ MergeWorker mergeworker; /* MergeWorker object for the same purpose */ memset(&merge, 0, sizeof(Merge)); memset(&mergeworker, 0, sizeof(MergeWorker)); pNew->pMerge = &merge; mergeworker.pDb = pDb; mergeworker.pLevel = pNew; mergeworker.pCsr = pCsr; pCsr->pPrevMergePtr = &iCurrentPtr; /* Mark the separators array for the new level as a "phantom". */ mergeworker.bFlush = 1; /* Allocate the first page of the output segment. */ rc = mergeWorkerNextPage(&mergeworker, iLeftPtr); |
︙ | ︙ | |||
3413 3414 3415 3416 3417 3418 3419 | } if( rc==LSM_OK ){ sortedInvokeWorkHook(pDb); } #if 0 | | | 3501 3502 3503 3504 3505 3506 3507 3508 3509 3510 3511 3512 3513 3514 3515 | } if( rc==LSM_OK ){ sortedInvokeWorkHook(pDb); } #if 0 lsmSortedDumpStructure(pDb, pDb->pWorker, 1, 0, "new-toplevel"); #endif if( pnWrite ) *pnWrite = nWrite; pDb->pWorker->nWrite += nWrite; return rc; } |
︙ | ︙ | |||
3581 3582 3583 3584 3585 3586 3587 3588 3589 3590 3591 3592 3593 3594 | pMW->pCsr = pCsr; /* Load the current output page into memory. */ if( rc==LSM_OK ) rc = mergeWorkerLoadOutputPage(pMW); /* Position the cursor. */ if( rc==LSM_OK ){ if( pMW->pPage==0 ){ /* The output array is still empty. So position the cursor at the very ** start of the input. */ rc = multiCursorEnd(pCsr, 0); }else{ /* The output array is non-empty. Position the cursor based on the ** page/cell data saved in the Merge.aInput[] array. */ | > | 3669 3670 3671 3672 3673 3674 3675 3676 3677 3678 3679 3680 3681 3682 3683 | pMW->pCsr = pCsr; /* Load the current output page into memory. */ if( rc==LSM_OK ) rc = mergeWorkerLoadOutputPage(pMW); /* Position the cursor. */ if( rc==LSM_OK ){ pCsr->pPrevMergePtr = &pMerge->iCurrentPtr; if( pMW->pPage==0 ){ /* The output array is still empty. So position the cursor at the very ** start of the input. */ rc = multiCursorEnd(pCsr, 0); }else{ /* The output array is non-empty. Position the cursor based on the ** page/cell data saved in the Merge.aInput[] array. */ |
︙ | ︙ | |||
3786 3787 3788 3789 3790 3791 3792 | SegmentPtr *pGobble = &mergeworker.pCsr->aPtr[i]; if( pGobble->pSeg->iRoot ){ rc = sortedBtreeGobble(pDb, mergeworker.pCsr, i); }else if( mergeworker.aGobble[i] ){ lsmFsGobble(pDb, pGobble->pSeg, &mergeworker.aGobble[i], 1); } } | < < < < < < < < < < < < < | 3875 3876 3877 3878 3879 3880 3881 3882 3883 3884 3885 3886 3887 3888 | SegmentPtr *pGobble = &mergeworker.pCsr->aPtr[i]; if( pGobble->pSeg->iRoot ){ rc = sortedBtreeGobble(pDb, mergeworker.pCsr, i); }else if( mergeworker.aGobble[i] ){ lsmFsGobble(pDb, pGobble->pSeg, &mergeworker.aGobble[i], 1); } } }else if( pLevel->lhs.iFirst==0 ){ /* If the new level is completely empty, remove it from the ** database snapshot. This can only happen if all input keys were ** annihilated. Since keys are only annihilated if the new level ** is the last in the linked list (contains the most ancient of ** database content), this guarantees that pLevel->pNext==0. */ |
︙ | ︙ | |||
3848 3849 3850 3851 3852 3853 3854 3855 3856 3857 3858 | /* Clean up the MergeWorker object initialized above. If no error ** has occurred, invoke the work-hook to inform the application that ** the database structure has changed. */ mergeWorkerShutdown(&mergeworker, &rc); if( rc==LSM_OK ) sortedInvokeWorkHook(pDb); /* If bFlush is true and the database is no longer considered "full", ** break out of the loop even if nRemaining is still greater than ** zero. The caller has an in-memory tree to flush to disk. */ if( bFlush && sortedDbIsFull(pDb)==0 ) break; | > > > > > < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < | 3924 3925 3926 3927 3928 3929 3930 3931 3932 3933 3934 3935 3936 3937 3938 3939 3940 3941 3942 3943 3944 3945 3946 3947 3948 3949 3950 3951 3952 3953 3954 3955 3956 3957 3958 | /* Clean up the MergeWorker object initialized above. If no error ** has occurred, invoke the work-hook to inform the application that ** the database structure has changed. */ mergeWorkerShutdown(&mergeworker, &rc); if( rc==LSM_OK ) sortedInvokeWorkHook(pDb); #if 0 lsmSortedDumpStructure(pDb, pDb->pWorker, 1, 0, "work"); #endif assertRunInOrder(pDb, &pLevel->lhs); /* If bFlush is true and the database is no longer considered "full", ** break out of the loop even if nRemaining is still greater than ** zero. The caller has an in-memory tree to flush to disk. */ if( bFlush && sortedDbIsFull(pDb)==0 ) break; } } if( pnWrite ) *pnWrite = (nWork - nRemaining); pWorker->nWrite += (nWork - nRemaining); #ifdef LSM_LOG_WORK lsmLogMessage(pDb, rc, "sortedWork(): %d pages", (nWork-nRemaining)); #endif return rc; } /* ** The database connection passed as the first argument must be a worker ** connection. This function checks if there exists an "old" in-memory tree ** ready to be flushed to disk. If so, *pbOut is set to true before ** returning. Otherwise false. ** ** Normally, LSM_OK is returned. Or, if an error occurs, an LSM error code. |
︙ | ︙ | |||
4354 4355 4356 4357 4358 4359 4360 | }else{ lsmStringAppendf(pStr, "%c", isalnum(z[iChar]) ?z[iChar] : '.'); } } return LSM_OK; } | > > > | > > > > > > > > > > | 4385 4386 4387 4388 4389 4390 4391 4392 4393 4394 4395 4396 4397 4398 4399 4400 4401 4402 4403 4404 4405 4406 4407 4408 4409 4410 4411 4412 4413 4414 4415 4416 | }else{ lsmStringAppendf(pStr, "%c", isalnum(z[iChar]) ?z[iChar] : '.'); } } return LSM_OK; } #define INFO_PAGE_DUMP_DATA 0x01 #define INFO_PAGE_DUMP_VALUES 0x02 #define INFO_PAGE_DUMP_HEX 0x04 static int infoPageDump( lsm_db *pDb, /* Database handle */ Pgno iPg, /* Page number of page to dump */ int flags, char **pzOut /* OUT: lsmMalloc'd string */ ){ int rc = LSM_OK; /* Return code */ Page *pPg = 0; /* Handle for page iPg */ int i, j; /* Loop counters */ const int perLine = 16; /* Bytes per line in the raw hex dump */ int bValues = (flags & INFO_PAGE_DUMP_VALUES); int bHex = (flags & INFO_PAGE_DUMP_HEX); int bData = (flags & INFO_PAGE_DUMP_DATA); *pzOut = 0; if( iPg==0 ) return LSM_ERROR; rc = lsmFsDbPageGet(pDb->pFS, iPg, &pPg); if( rc==LSM_OK ){ Blob blob = {0, 0, 0, 0}; |
︙ | ︙ | |||
4400 4401 4402 4403 4404 4405 4406 4407 4408 4409 4410 4411 4412 | for(iCell=0; iCell<nRec; iCell++){ u8 *aKey; int nKey = 0; /* Key */ u8 *aVal; int nVal = 0; /* Value */ int iPgPtr; int eType; char cType = '?'; Pgno iAbsPtr; infoCellDump(pDb, pPg, iCell, &eType, &iPgPtr, &aKey, &nKey, &aVal, &nVal, &blob ); iAbsPtr = iPgPtr + ((flags & SEGMENT_BTREE_FLAG) ? 0 : iPtr); | > < | < | | | > | | | | | | | | | | | | | | | | | | | | | | > > > > > > > > > > > > > > > > > > > | 4444 4445 4446 4447 4448 4449 4450 4451 4452 4453 4454 4455 4456 4457 4458 4459 4460 4461 4462 4463 4464 4465 4466 4467 4468 4469 4470 4471 4472 4473 4474 4475 4476 4477 4478 4479 4480 4481 4482 4483 4484 4485 4486 4487 4488 4489 4490 4491 4492 4493 4494 4495 4496 4497 4498 4499 4500 4501 4502 4503 4504 4505 4506 4507 4508 4509 4510 4511 4512 4513 4514 4515 4516 4517 4518 4519 4520 4521 4522 4523 4524 4525 4526 4527 4528 4529 4530 4531 4532 4533 4534 4535 4536 4537 4538 4539 4540 4541 4542 4543 | for(iCell=0; iCell<nRec; iCell++){ u8 *aKey; int nKey = 0; /* Key */ u8 *aVal; int nVal = 0; /* Value */ int iPgPtr; int eType; char cType = '?'; Pgno iAbsPtr; char zFlags[8]; infoCellDump(pDb, pPg, iCell, &eType, &iPgPtr, &aKey, &nKey, &aVal, &nVal, &blob ); iAbsPtr = iPgPtr + ((flags & SEGMENT_BTREE_FLAG) ? 0 : iPtr); lsmFlagsToString(eType, zFlags); lsmStringAppendf(&str, "%s %d (%s) ", zFlags, iAbsPtr, (rtTopic(eType) ? "sys" : "usr") ); infoAppendBlob(&str, bHex, aKey, nKey); if( nVal>0 && bValues ){ lsmStringAppendf(&str, "%*s", nKeyWidth - (nKey*(1+bHex)), ""); lsmStringAppendf(&str, " "); infoAppendBlob(&str, bHex, aVal, nVal); } lsmStringAppendf(&str, "\n"); } if( bData ){ lsmStringAppendf(&str, "\n-------------------" "-------------------------------------------------------------\n"); lsmStringAppendf(&str, "Page %d\n", iPg, (iPg-1)*nData, iPg*nData - 1); for(i=0; i<nData; i += perLine){ lsmStringAppendf(&str, "%04x: ", i); for(j=0; j<perLine; j++){ if( i+j>nData ){ lsmStringAppendf(&str, " "); }else{ lsmStringAppendf(&str, "%02x ", aData[i+j]); } } lsmStringAppendf(&str, " "); for(j=0; j<perLine; j++){ if( i+j>nData ){ lsmStringAppendf(&str, " "); }else{ lsmStringAppendf(&str,"%c", isprint(aData[i+j]) ? aData[i+j] : '.'); } } lsmStringAppendf(&str,"\n"); } } *pzOut = str.z; sortedBlobFree(&blob); lsmFsPageRelease(pPg); } return rc; } int lsmInfoPageDump( lsm_db *pDb, /* Database handle */ Pgno iPg, /* Page number of page to dump */ int bHex, /* True to output key/value in hex form */ char **pzOut /* OUT: lsmMalloc'd string */ ){ int flags = INFO_PAGE_DUMP_DATA | INFO_PAGE_DUMP_VALUES; if( bHex ) flags |= INFO_PAGE_DUMP_HEX; return infoPageDump(pDb, iPg, flags, pzOut); } void sortedDumpSegment(lsm_db *pDb, Segment *pRun, int bVals){ assert( pDb->xLog ); if( pRun && pRun->iFirst ){ int flags = (bVals ? INFO_PAGE_DUMP_VALUES : 0); char *zSeg; Page *pPg; zSeg = segToString(pDb->pEnv, pRun, 0); lsmLogMessage(pDb, LSM_OK, "Segment: %s", zSeg); lsmFree(pDb->pEnv, zSeg); lsmFsDbPageGet(pDb->pFS, pRun->iFirst, &pPg); while( pPg ){ Page *pNext; char *z = 0; infoPageDump(pDb, lsmFsPageNumber(pPg), flags, &z); lsmLogMessage(pDb, LSM_OK, "%s", z); lsmFree(pDb->pEnv, z); #if 0 sortedDumpPage(pDb, pRun, pPg, bVals); #endif lsmFsDbPageNext(pRun, pPg, 1, &pNext); lsmFsPageRelease(pPg); pPg = pNext; } } } |
︙ | ︙ |
Changes to src/lsm_tree.c.
︙ | ︙ | |||
121 122 123 124 125 126 127 128 129 130 131 132 133 134 | || (keyflags & LSM_POINT_DELETE)==0 ); return 1; } static int assert_delete_ranges_match(lsm_db *); #endif /* ** Container for a key-value pair. Within the *-shm file, each key/value ** pair is stored in a single allocation (which may not actually be ** contiguous in memory). Layout is the TreeKey structure, followed by ** the nKey bytes of key blob, followed by the nValue bytes of value blob | > | 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 | || (keyflags & LSM_POINT_DELETE)==0 ); return 1; } static int assert_delete_ranges_match(lsm_db *); static int treeCountEntries(lsm_db *db); #endif /* ** Container for a key-value pair. Within the *-shm file, each key/value ** pair is stored in a single allocation (which may not actually be ** contiguous in memory). Layout is the TreeKey structure, followed by ** the nKey bytes of key blob, followed by the nValue bytes of value blob |
︙ | ︙ | |||
442 443 444 445 446 447 448 449 | ** Append nIndent space (0x20) characters to string *pStr. */ static void lsmAppendIndent(LsmString *pStr, int nIndent){ int i; lsmStringExtend(pStr, nIndent); for(i=0; i<nIndent; i++) lsmStringAppend(pStr, " ", 1); } | < | | > > > > > > > > > > > > | > > | > > | > | 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 | ** Append nIndent space (0x20) characters to string *pStr. */ static void lsmAppendIndent(LsmString *pStr, int nIndent){ int i; lsmStringExtend(pStr, nIndent); for(i=0; i<nIndent; i++) lsmStringAppend(pStr, " ", 1); } void lsmFlagsToString(int flags, char *zFlags){ zFlags[0] = (flags & LSM_END_DELETE) ? ']' : '.'; /* Only one of LSM_POINT_DELETE, LSM_INSERT and LSM_SEPARATOR should ever ** be set. If this is not true, write a '?' to the output. */ switch( flags & (LSM_POINT_DELETE|LSM_INSERT|LSM_SEPARATOR) ){ case 0: zFlags[1] = '.'; break; case LSM_POINT_DELETE: zFlags[1] = '-'; break; case LSM_INSERT: zFlags[1] = '+'; break; case LSM_SEPARATOR: zFlags[1] = '^'; break; default: zFlags[1] = '?'; break; } zFlags[2] = (flags & LSM_SYSTEMKEY) ? '*' : '.'; zFlags[3] = (flags & LSM_START_DELETE) ? '[' : '.'; zFlags[4] = '\0'; } static void strAppendFlags(LsmString *pStr, u8 flags){ char zFlags[8]; lsmFlagsToString(flags, zFlags); zFlags[4] = ':'; lsmStringAppend(pStr, zFlags, 5); } void dump_node_contents( lsm_db *pDb, |
︙ | ︙ | |||
486 487 488 489 490 491 492 | TreeKey *pKey = treeShmkey(pDb, pNode->aiKeyPtr[i], TK_LOADKEY, &b,&rc); strAppendFlags(&s, pKey->flags); lsmAppendStrBlob(&s, TK_KEY(pKey), pKey->nKey); lsmStringAppend(&s, " ", -1); } } | > | > > | | 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 | TreeKey *pKey = treeShmkey(pDb, pNode->aiKeyPtr[i], TK_LOADKEY, &b,&rc); strAppendFlags(&s, pKey->flags); lsmAppendStrBlob(&s, TK_KEY(pKey), pKey->nKey); lsmStringAppend(&s, " ", -1); } } printf("% 6d %.*sleaf%.*s: %s\n", iNode, nPath, zPath, 20-nPath-4, zSpace, s.z ); lsmStringClear(&s); }else{ for(i=0; i<4 && nHeight>0; i++){ u32 iPtr = getChildPtr(pNode, pDb->treehdr.root.iTransId, i); zPath[nPath] = i+'0'; zPath[nPath+1] = '/'; if( iPtr ){ dump_node_contents(pDb, iPtr, zPath, nPath+2, nHeight-1); } if( i!=3 && pNode->aiKeyPtr[i] ){ TreeKey *pKey = treeShmkey(pDb, pNode->aiKeyPtr[i], TK_LOADKEY, &b,&rc); lsmStringInit(&s, pDb->pEnv); strAppendFlags(&s, pKey->flags); lsmAppendStrBlob(&s, TK_KEY(pKey), pKey->nKey); printf("% 6d %.*s%.*s: %s\n", iNode, nPath+1, zPath, 20-nPath-1, zSpace, s.z); lsmStringClear(&s); } } } tblobFree(pDb, &b); } |
︙ | ︙ | |||
1554 1555 1556 1557 1558 1559 1560 | assert( pNode->aiKeyPtr[iSlot] ); assert( iSlot==0 || iSlot==1 || iSlot==2 ); assert( (pCsr->iNode==(db->treehdr.root.nHeight-1))==(iNewptr==0) ); bLeaf = (pCsr->iNode==(p->nHeight-1) && p->nHeight>1); if( pNode->aiKeyPtr[0] || pNode->aiKeyPtr[2] ){ | | | | | > | | > | 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 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 | assert( pNode->aiKeyPtr[iSlot] ); assert( iSlot==0 || iSlot==1 || iSlot==2 ); assert( (pCsr->iNode==(db->treehdr.root.nHeight-1))==(iNewptr==0) ); bLeaf = (pCsr->iNode==(p->nHeight-1) && p->nHeight>1); if( pNode->aiKeyPtr[0] || pNode->aiKeyPtr[2] ){ /* There are currently at least 2 keys on this node. So just create ** a new copy of the node with one of the keys removed. If the node ** happens to be the root node of the tree, allocate an entire ** TreeNode structure instead of just a TreeLeaf. */ TreeNode *pNew; u32 iNew; if( bLeaf ){ pNew = (TreeNode *)newTreeLeaf(db, &iNew, &rc); }else{ pNew = newTreeNode(db, &iNew, &rc); } if( pNew ){ int i; int iOut = 1; for(i=0; i<4; i++){ if( i==iSlot ){ i++; if( bLeaf==0 ) pNew->aiChildPtr[iOut] = iNewptr; if( i<3 ) pNew->aiKeyPtr[iOut] = pNode->aiKeyPtr[i]; iOut++; }else if( bLeaf || p->nHeight==1 ){ if( i<3 && pNode->aiKeyPtr[i] ){ pNew->aiKeyPtr[iOut++] = pNode->aiKeyPtr[i]; } }else{ if( getChildPtr(pNode, WORKING_VERSION, i) ){ pNew->aiChildPtr[iOut] = getChildPtr(pNode, WORKING_VERSION, i); if( i<3 ) pNew->aiKeyPtr[iOut] = pNode->aiKeyPtr[i]; iOut++; } } } assert( iOut<=4 ); assert( bLeaf || pNew->aiChildPtr[0]==0 ); pCsr->iNode--; rc = treeUpdatePtr(db, pCsr, iNew); |
︙ | ︙ | |||
1770 1771 1772 1773 1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 | /* Step 1. This loop runs until the tree contains no keys within the ** range being deleted. Or until an error occurs. */ while( bDone==0 && rc==LSM_OK ){ int res; TreeCursor csr; /* Cursor to seek to first key in range */ void *pDel; int nDel; /* Key to (possibly) delete this iteration */ /* Seek the cursor to the first entry in the tree greater than pKey1. */ treeCursorInit(db, 0, &csr); lsmTreeCursorSeek(&csr, pKey1, nKey1, &res); if( res<=0 && lsmTreeCursorValid(&csr) ) lsmTreeCursorNext(&csr); /* If there is no such entry, or if it is greater than pKey2, then the ** tree now contains no keys in the range being deleted. In this case ** break out of the loop. */ bDone = 1; if( lsmTreeCursorValid(&csr) ){ | > > > | | 1792 1793 1794 1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 | /* Step 1. This loop runs until the tree contains no keys within the ** range being deleted. Or until an error occurs. */ while( bDone==0 && rc==LSM_OK ){ int res; TreeCursor csr; /* Cursor to seek to first key in range */ void *pDel; int nDel; /* Key to (possibly) delete this iteration */ #ifndef NDEBUG int nEntry = treeCountEntries(db); #endif /* Seek the cursor to the first entry in the tree greater than pKey1. */ treeCursorInit(db, 0, &csr); lsmTreeCursorSeek(&csr, pKey1, nKey1, &res); if( res<=0 && lsmTreeCursorValid(&csr) ) lsmTreeCursorNext(&csr); /* If there is no such entry, or if it is greater than pKey2, then the ** tree now contains no keys in the range being deleted. In this case ** break out of the loop. */ bDone = 1; if( lsmTreeCursorValid(&csr) ){ lsmTreeCursorKey(&csr, 0, &pDel, &nDel); if( db->xCmp(pDel, nDel, pKey2, nKey2)<0 ) bDone = 0; } if( bDone==0 ){ if( csr.iNode==(p->nHeight-1) ){ /* The element to delete already lies on a leaf node */ rc = treeDeleteEntry(db, &csr, 0); |
︙ | ︙ | |||
1823 1824 1825 1826 1827 1828 1829 1830 1831 | } } } } /* Clean up any memory allocated by the cursor. */ tblobFree(db, &csr.blob); } | > > > > > | > > | > > | > | 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 | } } } } /* Clean up any memory allocated by the cursor. */ tblobFree(db, &csr.blob); #if 0 dump_tree_contents(db, "ddd delete"); #endif assert( bDone || treeCountEntries(db)==(nEntry-1) ); } #if 0 dump_tree_contents(db, "during delete"); #endif /* Now insert the START_DELETE and END_DELETE keys. */ if( rc==LSM_OK ){ rc = treeInsertEntry(db, LSM_START_DELETE, pKey1, nKey1, 0, -1); } #if 0 dump_tree_contents(db, "during delete 2"); #endif if( rc==LSM_OK ){ rc = treeInsertEntry(db, LSM_END_DELETE, pKey2, nKey2, 0, -1); } #if 0 dump_tree_contents(db, "after delete"); #endif tblobFree(db, &blob); assert( assert_delete_ranges_match(db) ); return rc; } /* |
︙ | ︙ | |||
2167 2168 2169 2170 2171 2172 2173 | } pCsr->aiCell[pCsr->iNode] = iCell - (iNodePtr==0 && bLast); } return rc; } | > > > > > > > > > > > > > | > | 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 | } pCsr->aiCell[pCsr->iNode] = iCell - (iNodePtr==0 && bLast); } return rc; } int lsmTreeCursorFlags(TreeCursor *pCsr){ int flags = 0; if( pCsr && pCsr->iNode>=0 ){ int rc = LSM_OK; TreeKey *pKey = (TreeKey *)treeShmptr(pCsr->pDb, pCsr->apTreeNode[pCsr->iNode]->aiKeyPtr[pCsr->aiCell[pCsr->iNode]], &rc ); assert( rc==LSM_OK ); flags = pKey->flags; } return flags; } int lsmTreeCursorKey(TreeCursor *pCsr, int *pFlags, void **ppKey, int *pnKey){ TreeKey *pTreeKey; int rc = LSM_OK; assert( lsmTreeCursorValid(pCsr) ); pTreeKey = pCsr->pSave; if( !pTreeKey ){ pTreeKey = csrGetKey(pCsr, &pCsr->blob, &rc); } if( rc==LSM_OK ){ *pnKey = pTreeKey->nKey; if( pFlags ) *pFlags = pTreeKey->flags; *ppKey = (void *)&pTreeKey[1]; } return rc; } int lsmTreeCursorValue(TreeCursor *pCsr, void **ppVal, int *pnVal){ |
︙ | ︙ | |||
2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 | } pShm->bWriter = 0; intArrayFree(pDb->pEnv, &pDb->rollback); return LSM_OK; } static int assert_delete_ranges_match(lsm_db *db){ int prev = 0; TreeBlob blob = {0, 0}; TreeCursor csr; /* Cursor used to iterate through tree */ int rc; | > < > > > > > > > > > > > > > > > > > > > | 2390 2391 2392 2393 2394 2395 2396 2397 2398 2399 2400 2401 2402 2403 2404 2405 2406 2407 2408 2409 2410 2411 2412 2413 2414 2415 2416 2417 2418 2419 2420 2421 2422 2423 2424 2425 2426 2427 2428 2429 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439 | } pShm->bWriter = 0; intArrayFree(pDb->pEnv, &pDb->rollback); return LSM_OK; } #ifndef NDEBUG static int assert_delete_ranges_match(lsm_db *db){ int prev = 0; TreeBlob blob = {0, 0}; TreeCursor csr; /* Cursor used to iterate through tree */ int rc; treeCursorInit(db, 0, &csr); for( rc = lsmTreeCursorEnd(&csr, 0); rc==LSM_OK && lsmTreeCursorValid(&csr); rc = lsmTreeCursorNext(&csr) ){ TreeKey *pKey = csrGetKey(&csr, &blob, &rc); if( rc!=LSM_OK ) break; assert( ((prev&LSM_START_DELETE)==0)==((pKey->flags&LSM_END_DELETE)==0) ); prev = pKey->flags; } tblobFree(csr.pDb, &csr.blob); return 1; } static int treeCountEntries(lsm_db *db){ TreeCursor csr; /* Cursor used to iterate through tree */ int rc; int nEntry = 0; treeCursorInit(db, 0, &csr); for( rc = lsmTreeCursorEnd(&csr, 0); rc==LSM_OK && lsmTreeCursorValid(&csr); rc = lsmTreeCursorNext(&csr) ){ nEntry++; } tblobFree(csr.pDb, &csr.blob); return nEntry; } #endif |