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: 8140c0abefd0a9889c26c0235c875b7043a3e6af
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
Unified Diff Ignore Whitespace Patch
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
49
50
51
52
53
54





55
56
57
58




59
60
61
62
63




64
65
66
67
68
69
70
#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

/*
** 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]);
}





static u16 btGetU16(const u8 *a){
  return ((u32)a[0] << 8) + (u32)a[1];
}





static void btPutU16(u8 *a, u16 i){
  a[0] = (u8)((i>>8) & 0xFF);
  a[1] = (u8)((i>>0) & 0xFF);
}





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);
}








>
>
>

















|
|




>
>
>
>
>




>
>
>
>





>
>
>
>







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
1269
1270
1271
1272
1273
1274
1275
1276
    }
  }

  rc = btSetChildPgno(
      pDb, pPar, iSib+ctx.nIn-1, sqlite4BtPagePgno(ctx.apPg[ctx.nOut-1])
  );
  if( rc==SQLITE4_OK ){
    pCsr->nPg--;
    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 ){







|







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

1544
1545

1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
  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 ){
      rc = btCsrSeek(&csr, pK, nK, BT_SEEK_GE, 1);

    }
  }
  if( rc==SQLITE4_OK ) rc = btErrorBkpt(SQLITE4_CORRUPT);

  if( 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);
  }







>
|

>


<

|







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);
  }