SQLite4  Check-in [6b27bf4069]

TESTFIXTURE_PREREQ  = $(TESTSRC) $(TESTSRC2) 
TESTFIXTURE_PREREQ += $(TOP)/src/tclsqlite.c
TESTFIXTURE_PREREQ += libsqlite4.a

testfixture$(EXE): $(TESTFIXTURE_PREREQ)
	$(TCCX) $(TCL_FLAGS) -DTCLSH=1 $(TESTFIXTURE_FLAGS)                  \
		$(TESTSRC) $(TESTSRC2) $(TOP)/src/tclsqlite.c                \
		-o testfixture$(EXE) $(LIBTCL) $(THREADLIB) libsqlite4.a

amalgamation-testfixture$(EXE): sqlite4.c $(TESTSRC) $(TOP)/src/tclsqlite.c
	$(TCCX) $(TCL_FLAGS) -DTCLSH=1 $(TESTFIXTURE_FLAGS)                  \
		$(TESTSRC) $(TOP)/src/tclsqlite.c sqlite4.c                  \
		-o testfixture$(EXE) $(LIBTCL) $(THREADLIB)

fts3-testfixture$(EXE): sqlite4.c fts3amal.c $(TESTSRC) $(TOP)/src/tclsqlite.c

  iOff += nShift;
  mask = mask >> nShift;

  pSnip->iOff = iOff;
  pSnip->hlmask = mask;
}


































static void fts5Snippet(sqlite4_context *pCtx, int nArg, sqlite4_value **apArg){
  Snippet aSnip[4];
  int nSnip;
  int iCol = -1;
  int nToken = -15;
  int rc;

    memset(aSnip, 0, sizeof(aSnip));
    for(i=0; rc==SQLITE4_OK && i<nSnip; i++){
      rc = fts5BestSnippet(pCtx, iCol, &mask, nTok, &aSnip[i]);
    }
    if( mask==0 || nSnip==4 ){
      SnippetText text = {0, 0, 0};

      for(i=0; rc==SQLITE4_OK && i<nSnip; i++){
        int nSz;
        rc = sqlite4_mi_size(pCtx, aSnip[i].iCol, -1, &nSz);
        if( rc==SQLITE4_OK ){
          fts5SnippetImprove(pCtx, nTok, nSz, &aSnip[i]);
          rc = fts5SnippetText(
              pCtx, &aSnip[i], &text, nTok, zStart, zEnd, zEllipses

  if( rc!=LSM_OK ){
    lsmFree(pEnv, zAlloc);
    zAlloc = 0;
  }
  *pzAbs = zAlloc;
  return rc;
}




















/*
** Open a new connection to database zFilename.
*/
int lsm_open(lsm_db *pDb, const char *zFilename){
  int rc;

      if( rc==LSM_OK && LSM_OK==(rc = lsmCheckpointLoad(pDb, 0)) ){
        lsmFsSetPageSize(pDb->pFS, lsmCheckpointPgsz(pDb->aSnapshot));
        lsmFsSetBlockSize(pDb->pFS, lsmCheckpointBlksz(pDb->aSnapshot));
      }
    }

    lsmFree(pDb->pEnv, zFull);

  }

  assert( pDb->bReadonly==0 || pDb->bReadonly==1 );
  assert( rc!=LSM_OK || (pDb->pShmhdr==0)==(pDb->bReadonly==1) );

  return rc;
}


int lsm_close(lsm_db *pDb){
  int rc = LSM_OK;
  if( pDb ){
    assert_db_state(pDb);
    if( pDb->pCsr || pDb->nTransOpen ){
      rc = LSM_MISUSE_BKPT;
    }else{
      lsmFreeSnapshot(pDb->pEnv, pDb->pClient);
      pDb->pClient = 0;



      lsmDbDatabaseRelease(pDb);
      lsmLogClose(pDb);
      lsmFsClose(pDb->pFS);
      assert( pDb->mLock==0 );
      
      /* Invoke any destructors registered for the compression or 

          }
        }
      }
    }

    if( pDb->iRwclient>=0 ){
      lsmShmLock(pDb, LSM_LOCK_RWCLIENT(pDb->iRwclient), LSM_LOCK_UNLOCK, 0);

    }

    lsmShmLock(pDb, LSM_LOCK_DMS2, LSM_LOCK_UNLOCK, 0);
    lsmShmLock(pDb, LSM_LOCK_DMS1, LSM_LOCK_UNLOCK, 0);
  }
  pDb->pShmhdr = 0;
}

      if( rc2!=LSM_BUSY ){
        rc = rc2;
        break;
      }
    }
  }
  lsmShmLock(pDb, LSM_LOCK_DMS1, LSM_LOCK_UNLOCK, 0);

  return rc;
}

static int dbOpenSharedFd(lsm_env *pEnv, Database *p, int bRoOk){
  int rc;

  rc = lsmEnvOpen(pEnv, p->zName, 0, &p->pFile);

      case LSM_LOCK_SHARED:
        if( nExcl ){
          rc = LSM_BUSY;
        }else{
          if( nShared==0 ){
            rc = lockSharedFile(db->pEnv, p, iLock, LSM_LOCK_SHARED);
          }

          db->mLock |= ms;
          db->mLock &= ~me;

        }
        break;

      default:
        assert( eOp==LSM_LOCK_EXCL );
        if( nExcl || nShared ){
          rc = LSM_BUSY;
        }else{
          rc = lockSharedFile(db->pEnv, p, iLock, LSM_LOCK_EXCL);

          db->mLock |= (me|ms);

        }
        break;
    }

    lsmMutexLeave(db->pEnv, p->pClientMutex);
  }

  INSERT INTO t1 SELECT randstr(100,100), randstr(100,100) FROM t1;   --  4K
  INSERT INTO t1 SELECT randstr(100,100), randstr(100,100) FROM t1;   --  8K
  INSERT INTO t1 SELECT randstr(100,100), randstr(100,100) FROM t1;   -- 16K
  INSERT INTO t1 SELECT randstr(100,100), randstr(100,100) FROM t1;   -- 32K
  INSERT INTO t1 SELECT randstr(100,100), randstr(100,100) FROM t1;   -- 64K
}
do_test 3.2 {
  sqlite4_lsm_flush db main
  sqlite4_lsm_work db main -nmerge 1 -npage 1000000
  execsql { SELECT count(*) FROM t1 }
} {65536}
do_test 3.3 {
  db close
  sqlite4 db test.db
  execsql { SELECT count(*) FROM t1 }
} {65536}
do_test 3.4 {
  execsql { INSERT INTO t1 VALUES(randstr(100,100), randstr(100,100)) }

  sqlite4_lsm_flush db main
  sqlite4_lsm_work db main -nmerge 1 -npage 1000000
  execsql { SELECT count(*) FROM t1 }
} {65537}

finish_test

# tree to be flushed to disk, 
#
populate_db_2
do_execsql_test 3.1 {
  BEGIN;
    INSERT INTO t1 VALUES(10, randstr(910, 910));
}
do_test 3.2 { sqlite4_lsm_config db main autoflush } [expr 1*1024*1024]
do_test 3.3 { sqlite4_lsm_config db main autoflush 4096 } 4096

do_test 3.4 {
  set res [list]
  db eval { SELECT a, length(b) AS l FROM t1 } {
    lappend res $a $l
    # The following commit will flush the in-memory tree to disk.
    if {$a == 5} { db eval COMMIT }

do_test 1.7 { sqlite4_lsm_config db main safety    } {2}
do_test 1.8 { sqlite4_lsm_config db main safety 3  } {2}
do_test 1.9 { sqlite4_lsm_config db main safety    } {2}

#-------------------------------------------------------------------------
reset_db
do_test 2.0 { sqlite4_lsm_config db main safety   2    } {2}
do_test 2.1 { sqlite4_lsm_config db main log-size 1024 } {1024}

do_execsql_test 2.2 {
  CREATE TABLE t1(a PRIMARY KEY, b);
  INSERT INTO t1 VALUES(randstr(50,50), randstr(50,50));
} {}
do_filesize_test 2.3   0 1024

do_execsql_test 2.4 {
  BEGIN;
    INSERT INTO t1 VALUES(randstr(50,50), randstr(50,50));
    INSERT INTO t1 VALUES(randstr(50,50), randstr(50,50));
    INSERT INTO t1 VALUES(randstr(50,50), randstr(50,50));
    INSERT INTO t1 VALUES(randstr(50,50), randstr(50,50));
    INSERT INTO t1 VALUES(randstr(50,50), randstr(50,50));
    INSERT INTO t1 VALUES(randstr(50,50), randstr(50,50));
  COMMIT;
} {}
do_filesize_test 2.5   0 2048

do_test         2.6 { sqlite4_lsm_flush db main } {}
do_execsql_test 2.7 { INSERT INTO t1 VALUES(randstr(50,50), randstr(50,50)) }
do_test         2.8 { sqlite4_lsm_checkpoint db main } {}
do_test 2.9 { sqlite4_lsm_info db main log-structure } {0 0 0 0 2560 3072}

for {set i 1} {$i <= 6} {incr i} {
  do_execsql_test 2.10.$i.1 {
    INSERT INTO t1 VALUES(randstr(50,50), randstr(50,50));
  }
  do_execsql_test 2.10.$i.2 { SELECT count(*) FROM t1 } [expr 8 + $i]
  do_recover_test 2.10.$i.3 { SELECT count(*) FROM t1 } [expr 8 + $i]
}

do_test 2.11 { 
  sqlite4_lsm_info db main log-structure 
} {2560 3080 0 2216 3584 4608}


finish_test

  db write ccc three
  db write ddd four
  db write eee five
  db write fff six
  reopen
  db delete_range a bbb
  reopen
breakpoint
  db work 10 
} {1}

do_contents_test 2.2 { {bbb two} {ccc three} {ddd four} {eee five} {fff six} }


#-------------------------------------------------------------------------

} {1}

do_test 3.2 {
  db write bx seven
  reopen
  db delete_range aaa bx
  reopen
  db work 10
} {2}

do_contents_test 3.3 { 
  {aaa one} {bx seven} {ccc three} {ddd four} {eee five} {fff six}
}

do_test 3.4 { fetch ddd } four

  } else {
    set locked {0 {}}
  }

  # Open a single-process connection to the database from an external
  # process (if $tn==1, otherwise open it from within the current 
  # process).

  code2 { sqlite4 db2 file:test.db?lsm_multiple_processes=0 }

  # Try to open some other connections to the database file, both in multi
  # and single process mode. If ($tn==1), then all such attempts fail. Or,
  # if ($tn==2), they all succeed.
  do_test $tn.1 {
    catch { db close }

#
lappend ::testsuitelist xxx

test_suite "src4" -prefix "" -description {
} -files {
  simple.test simple2.test
  log3.test 
  lsm1.test lsm2.test
  csr1.test
  ckpt1.test
  mc1.test
  fts5expr1.test fts5query1.test fts5rnd1.test fts5create.test
  fts5snippet.test

  aggerror.test

do_execsql_test 3.1 { CREATE TABLE t1(k PRIMARY KEY, v UNIQUE) }

do_execsql_test 3.2 { 
  SELECT * FROM sqlite_master
} {
  table t1                    t1 2 {CREATE TABLE t1(k PRIMARY KEY, v UNIQUE)} 
  index sqlite_autoindex_t1_2 t1 3 {}
}

#explain { INSERT INTO t1 VALUES('one', '111') }
#execsql { PRAGMA vdbe_trace = 1 }
#execsql { PRAGMA kv_trace = 1 }
#
do_execsql_test 3.3 { INSERT INTO t1 VALUES('one', '111') } {}

do_execsql_test 5.1 { CREATE TABLE t1(k, v UNIQUE) }
do_execsql_test 5.2 { CREATE INDEX i1 ON t1(v) }

do_execsql_test 5.3 { 
  SELECT * FROM sqlite_master
} {
  table t1                    t1 3 {CREATE TABLE t1(k, v UNIQUE)} 
  index sqlite_autoindex_t1_1 t1 2 {}
  index i1                    t1 4 {CREATE INDEX i1 ON t1(v)}
}

do_execsql_test 5.3 { INSERT INTO t1 VALUES('one', '111') } {}
do_execsql_test 5.4 { SELECT * FROM t1 } {one 111} 
do_execsql_test 5.5 { PRAGMA integrity_check } {ok}

  return LSM_OK;
}
static void testCompressNoopFree(void *pCtx){
}
/* 
** End of compression routines "noop".
*************************************************************************/



























































































































































/*
** TCLCMD:    sqlite4_lsm_config DB DBNAME PARAM ...
*/
static int test_sqlite4_lsm_config(
  void * clientData,
  Tcl_Interp *interp,
  int objc,
  Tcl_Obj *CONST objv[]
){
  struct Switch {
    const char *zSwitch;
    int iVal;
  } aParam[] = {
    { "safety",         LSM_CONFIG_SAFETY }, 
    { "autoflush",      LSM_CONFIG_AUTOFLUSH }, 
    { "mmap",           LSM_CONFIG_MMAP }, 
    { "page-size",      LSM_CONFIG_PAGE_SIZE }, 
    { "autowork",       LSM_CONFIG_AUTOWORK }, 
    { 0, 0 }
  };

  const char *zDb;                /* objv[1] as a string */
  const char *zName;              /* objv[2] as a string */
  int iParam;                     /* Second argument for lsm_config() */
  int iConfig = -1;               /* Third argument for lsm_config() */
  int rc;
  sqlite4 *db;
  lsm_db *pLsm;

  /* Process arguments. Return early if there is a problem. */
  if( objc!=4 && objc!=5 ){
    Tcl_WrongNumArgs(interp, 1, objv, "DB DBNAME PARAM ?VALUE?");
    return TCL_ERROR;
  }
  zDb = Tcl_GetString(objv[1]);
  zName = Tcl_GetString(objv[2]);
  rc = Tcl_GetIndexFromObjStruct(
      interp, objv[3], aParam, sizeof(aParam[0]), "param", 0, &iParam
  );
  if( rc!=TCL_OK ) return rc;
  if( rc==TCL_OK ){
    iParam = aParam[iParam].iVal;
    rc = getDbPointer(interp, zDb, &db);
  }
  if( rc==TCL_OK && objc==5 ){
    rc = Tcl_GetIntFromObj(interp, objv[4], &iConfig);
  }
  if( rc!=TCL_OK ) return rc;

  rc = sqlite4_kvstore_control(db, zName, SQLITE4_KVCTRL_LSM_HANDLE, &pLsm);
  if( rc==SQLITE4_OK ){
    rc = lsm_config(pLsm, iParam, &iConfig);
    Tcl_SetObjResult(interp, Tcl_NewIntObj(iConfig));

  }


  if( rc!=SQLITE4_OK ){
    Tcl_SetResult(interp, (char *)sqlite4TestErrorName(rc), TCL_STATIC);
    return TCL_ERROR;
  }
  return TCL_OK;
}

/*
** TCLCMD:    sqlite4_lsm_info DB DBNAME PARAM
*/
static int test_sqlite4_lsm_info(
  void * clientData,

    return TCL_ERROR;
  }

  Tcl_ResetResult(interp);
  return TCL_OK;
}

/*
** TCLCMD:    sqlite4_lsm_flush DB DBNAME 
*/
static int test_sqlite4_lsm_flush(
  void * clientData,
  Tcl_Interp *interp,
  int objc,
  Tcl_Obj *CONST objv[]
){
  const char *zDb;
  const char *zName;
  int rc;
  sqlite4 *db;
  lsm_db *pLsm;

  if( objc!=3 ){
    Tcl_WrongNumArgs(interp, 1, objv, "DB DBNAME");
    return TCL_ERROR;
  }
  zDb = Tcl_GetString(objv[1]);
  zName = Tcl_GetString(objv[2]);

  rc = getDbPointer(interp, zDb, &db);
  if( rc!=TCL_OK ) return rc;

  rc = sqlite4_kvstore_control(db, zName, SQLITE4_KVCTRL_LSM_HANDLE, &pLsm);
  if( rc==SQLITE4_OK ){
    int nZero = 0;
    int nOrig = -1;
    lsm_config(pLsm, LSM_CONFIG_AUTOFLUSH, &nOrig);
    lsm_config(pLsm, LSM_CONFIG_AUTOFLUSH, &nZero);
    rc = lsm_begin(pLsm, 1);
    if( rc==LSM_OK ) rc = lsm_commit(pLsm, 0);
    lsm_config(pLsm, LSM_CONFIG_AUTOFLUSH, &nOrig);
  }
  if( rc!=SQLITE4_OK ){
    Tcl_SetResult(interp, (char *)sqlite4TestErrorName(rc), TCL_STATIC);
    return TCL_ERROR;
  }

  Tcl_ResetResult(interp);
  return TCL_OK;
}

static int testConfigureSetCompression(
  Tcl_Interp *interp, 
  lsm_db *db, 
  Tcl_Obj *pCmp,
  unsigned int iId
){
  struct CompressionScheme {
    const char *zName;
    lsm_compress cmp;
  } aCmp[] = {
    { "encrypt", { 0, 43, 
        testCompressEncBound, testCompressEncCompress,
        testCompressEncUncompress, testCompressEncFree
    } },
    { "rle", { 0, 44, 
        testCompressRleBound, testCompressRleCompress,
        testCompressRleUncompress, testCompressRleFree
    } },
    { "noop", { 0, 45, 
        testCompressNoopBound, testCompressNoopCompress,
        testCompressNoopUncompress, testCompressNoopFree
    } },
    { 0, {0, 0, 0, 0, 0, 0} }
  };
  int iOpt;
  int rc;

  if( interp ){
    rc = Tcl_GetIndexFromObjStruct(
        interp, pCmp, aCmp, sizeof(aCmp[0]), "scheme", 0, &iOpt
        );
    if( rc!=TCL_OK ) return rc;
  }else{
    int nOpt = sizeof(aCmp)/sizeof(aCmp[0]);
    for(iOpt=0; iOpt<nOpt; iOpt++){
      if( iId==aCmp[iOpt].cmp.iId ) break;
    }
    if( iOpt==nOpt ) return 0;
  }

  rc = lsm_config(db, LSM_CONFIG_SET_COMPRESSION, &aCmp[iOpt].cmp);
  return rc;
}

static int testCompressFactory(void *pCtx, lsm_db *db, unsigned int iId){
  return testConfigureSetCompression(0, db, 0, iId);
}

static int testConfigureSetFactory(
  Tcl_Interp *interp, 
  lsm_db *db, 
  Tcl_Obj *pArg
){
  lsm_compress_factory aFactory[2] = {
    { 0, 0, 0 },
    { 0, testCompressFactory, 0 },
  };
  int bArg = 0;
  int rc;

  rc = Tcl_GetBooleanFromObj(interp, pArg, &bArg);
  if( rc!=TCL_OK ) return rc;
  assert( bArg==1 || bArg==0 );

  rc = lsm_config(db, LSM_CONFIG_SET_COMPRESSION_FACTORY, &aFactory[bArg]);
  return rc;
}

static int testConfigureLsm(Tcl_Interp *interp, lsm_db *db, Tcl_Obj *pObj){
  struct Lsmconfig {
    const char *zOpt;
    int eOpt;
  } aConfig[] = {
    { "autoflush",               LSM_CONFIG_AUTOFLUSH },
    { "page_size",               LSM_CONFIG_PAGE_SIZE },
    { "block_size",              LSM_CONFIG_BLOCK_SIZE },
    { "safety",                  LSM_CONFIG_SAFETY },
    { "autowork",                LSM_CONFIG_AUTOWORK },
    { "autocheckpoint",          LSM_CONFIG_AUTOCHECKPOINT },
    { "mmap",                    LSM_CONFIG_MMAP },
    { "use_log",                 LSM_CONFIG_USE_LOG },
    { "automerge",               LSM_CONFIG_AUTOMERGE },
    { "max_freelist",            LSM_CONFIG_MAX_FREELIST },
    { "multi_proc",              LSM_CONFIG_MULTIPLE_PROCESSES },
    { "set_compression",         LSM_CONFIG_SET_COMPRESSION },
    { "set_compression_factory", LSM_CONFIG_SET_COMPRESSION_FACTORY },
    { "readonly",                LSM_CONFIG_READONLY },
    { 0, 0 }
  };
  int nElem;
  int i;
  Tcl_Obj **apElem;
  int rc;

  rc = Tcl_ListObjGetElements(interp, pObj, &nElem, &apElem);
  for(i=0; rc==TCL_OK && i<nElem; i+=2){
    int iOpt;
    rc = Tcl_GetIndexFromObjStruct(
        interp, apElem[i], aConfig, sizeof(aConfig[0]), "option", 0, &iOpt
    );
    if( rc==TCL_OK ){
      if( i==(nElem-1) ){
        Tcl_ResetResult(interp);
        Tcl_AppendResult(interp, "option \"", Tcl_GetString(apElem[i]), 
            "\" requires an argument", 0
            );
        rc = TCL_ERROR;
      }else{
        if( aConfig[iOpt].eOpt==LSM_CONFIG_SET_COMPRESSION ){
          rc = testConfigureSetCompression(interp, db, apElem[i+1], 0);
        }
        else if( aConfig[iOpt].eOpt==LSM_CONFIG_SET_COMPRESSION_FACTORY ){
          rc = testConfigureSetFactory(interp, db, apElem[i+1]);
        }
        else {
          int iVal;
          rc = Tcl_GetIntFromObj(interp, apElem[i+1], &iVal);
          if( rc==TCL_OK ){
            lsm_config(db, aConfig[iOpt].eOpt, &iVal);
          }
          Tcl_SetObjResult(interp, Tcl_NewIntObj(iVal));
        }
      }
    }
  }

  return rc;
}


typedef struct TclLsmCursor TclLsmCursor;
typedef struct TclLsm TclLsm;

struct TclLsm {
  lsm_db *db;
};

    case 9: assert( 0==strcmp(aCmd[9].zCmd, "flush") ); {
      rc = lsm_flush(p->db);
      return test_lsm_error(interp, "lsm_flush", rc);
    }

    case 10: assert( 0==strcmp(aCmd[10].zCmd, "config") ); {



      return testConfigureLsm(interp, p->db, objv[2]);


    }

    case 11: assert( 0==strcmp(aCmd[11].zCmd, "checkpoint") ); {
      rc = lsm_checkpoint(p->db, 0);
      return test_lsm_error(interp, "lsm_checkpoint", rc);
    }

  if( rc!=LSM_OK ){
    test_lsm_del((void *)p);
    test_lsm_error(interp, "lsm_new", rc);
    return TCL_ERROR;
  }

  if( objc==4 ){




    rc = testConfigureLsm(interp, p->db, objv[3]);

    if( rc!=TCL_OK ){ 
      test_lsm_del((void *)p);
      return rc;
    }
  }

  lsm_config_log(p->db, xLog, 0);

int SqlitetestLsm_Init(Tcl_Interp *interp){
  struct SyscallCmd {
    const char *zName;
    Tcl_ObjCmdProc *xCmd;
  } aCmd[] = {
    { "sqlite4_lsm_work",       test_sqlite4_lsm_work                },
    { "sqlite4_lsm_checkpoint", test_sqlite4_lsm_checkpoint          },
    { "sqlite4_lsm_flush",      test_sqlite4_lsm_flush               },
    { "sqlite4_lsm_info",       test_sqlite4_lsm_info                },
    { "sqlite4_lsm_config",     test_sqlite4_lsm_config              },
    { "lsm_open",               test_lsm_open                        },
  };
  int i;

  for(i=0; i<sizeof(aCmd)/sizeof(aCmd[0]); i++){
    Tcl_CreateObjCommand(interp, aCmd[i].zName, aCmd[i].xCmd, 0, 0);
  }
  return TCL_OK;
}

# Flush the in-memory tree to disk and merge all runs together into
# a single b-tree structure. Because this annihilates all delete keys,
# the next rowid allocated for each table with an IPK will be as expected
# by SQLite 3 tests.
#
proc optimize_db {} { 
  #catch { 

    sqlite4_lsm_flush db main 



    sqlite4_lsm_work db main -nmerge 1 -npage 100000 
    sqlite4_lsm_checkpoint db main
  #}
  return ""
}

<title>LSM Design Overview</title>
<nowiki>





<div id=start_of_toc></div>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#summary style=text-decoration:none>1. Summary </a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#locks style=text-decoration:none>2. Locks </a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#database_connect_and_disconnect_operations style=text-decoration:none>3. Database Connect and Disconnect Operations</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#read-write_clients style=text-decoration:none>3.1. Read-write clients</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#read-only_clients style=text-decoration:none>3.2. Read-only clients</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#data_structures style=text-decoration:none>4. Data Structures </a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#database_file style=text-decoration:none>4.1. Database file</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#sorted_runs style=text-decoration:none>4.1.1. Sorted Runs</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#levels style=text-decoration:none>4.1.2. Levels</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#snapshots style=text-decoration:none>4.1.3. Snapshots</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#in-memory_tree style=text-decoration:none>4.2. In-Memory Tree</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#memory_allocation style=text-decoration:none>4.2.1. Memory Allocation</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#header_fields style=text-decoration:none>4.2.2. Header Fields</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#other_shared-memory_fields style=text-decoration:none>4.3. Other Shared-Memory Fields</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#log_file style=text-decoration:none>4.4. Log file</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#database_operations style=text-decoration:none>5. Database Operations </a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#reading style=text-decoration:none>5.1. Reading</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#writing style=text-decoration:none>5.2. Writing</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#flushing_the_in-memory_tree_to_disk style=text-decoration:none>5.2.1. Flushing the in-memory tree to disk</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#shared-memory_management style=text-decoration:none>5.2.2. Shared-memory management</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#log_file_management style=text-decoration:none>5.2.3. Log file management</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#working style=text-decoration:none>5.3. Working</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#free-block_list_management style=text-decoration:none>5.3.1. Free-block list management</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=#checkpoint_operations style=text-decoration:none>5.4. Checkpoint Operations</a><br>

<div id=end_of_toc></div>

<h1 id=summary>1. Summary </h1>

  <li> Sweep the shared-memory area to rebuild the linked list of chunks so
       that it is consistent with the current tree-header.

  <li> Clear the writer flag.
</ol>

<h3 id=flushing_the_in-memory_tree_to_disk>5.2.1. Flushing the in-memory tree to disk</h3>

<p>
For the purposes of writing, the database file and the in-memory tree are
largely independent. Processes holding the WRITER lock write to the in-memory
tree, and processes holding the WORKER lock write to the database file.

<ol>
  <li> If a write transaction is open, write the new tree-header to
       shared-memory (as described above). Otherwise, if no write-transaction
       is open, open one - repairing the tree headers if required.

  <li> Execute a WORKER transaction (see "Working" below) to add a new level
       to the LSM. The new level contains the current contents of the 
       in-memory tree.

  <li> Update the private copy of the tree-header to reflect a new, empty tree.

  <li> Commit the write transaction, writing the new, empty tree to
       shared-memory.
</ol>

<h3 id=shared-memory_management>5.2.2. Shared-memory management</h3>

<p>
A writer client may have to allocate new shared-memory chunks. This can be
done either by extending the shared-memory region or by recycling the first
chunk in the linked-list. To check if the first chunk in the linked-list may
be reused, the writer must check that:

<ul>
  <li> The chunk is not part of the current in-memory tree (the one being
       appended to by the writer). A writer can check this by examining its
       private copy of the tree-header.

  <li> The chunk is not part of an in-memory tree being used by an existing
       reader. A writer checks this by scanning (and possibly updating) the
       values associated with the READER locks - similar to the way SQLite 
       does in WAL mode.
</ul>

<h3 id=log_file_management>5.2.3. Log file management</h3>

<p>
A writer client also writes to the log file. All information required to write
to the log file  (the offset to write to and the initial checksum values) is
embedded in the tree-header. Except, in order to reuse log file space (wrap
around to the start of the log file), a writer needs to know that the space
being recycled will not be required by any recovery process in the future.
In other words, that the information contained in the transactions being
overwritten has been written into the database file and is part of the
snapshot written into the database file by a checkpointer (see "Checkpoint
Operations" below).

<p>
To determine whether or not the log file can be wrapped, the writer requires
access to information stored in the newest snapshot written into the database
header. Their exists a shared-memory variable indicating which of the two
meta-pages contain this snapshot, but the writer process still has to read the
snapshot data and verify its checksum from disk.

<h2 id=working>5.3. Working</h2>

<p>
Working is similar to writing. The difference is that a "writer" modifies
the in-memory tree. A "worker" modifies the contents of the database file.

<ol>

  <li> Sync the database file again.

  <li> Update the shared-memory variable to indicate the meta-page written in
       step 5.

  <li> Drop the CHECKPOINTER lock.
</ol>