leveldb-haskell 0.0.3 → 0.1.0

raw patch · 116 files changed

+793/−25145 lines, 116 filesdep +data-defaultdep +resourcetdep +transformerssetup-changedPVP ok

version bump matches the API change (PVP)

Dependencies added: data-default, resourcet, transformers

API changes (from Hackage documentation)

Files

• Readme.md +22/−3
• Setup.hs +1/−1
• cbits/leveldb/db/builder.cc +0/−88
• cbits/leveldb/db/builder.h +0/−34
• cbits/leveldb/db/c.cc +0/−471
• cbits/leveldb/db/corruption_test.cc +0/−359
• cbits/leveldb/db/db_bench.cc +0/−877
• cbits/leveldb/db/db_impl.cc +0/−1444
• cbits/leveldb/db/db_impl.h +0/−192
• cbits/leveldb/db/db_iter.cc +0/−299
• cbits/leveldb/db/db_iter.h +0/−26
• cbits/leveldb/db/db_test.cc +0/−1711
• cbits/leveldb/db/dbformat.cc +0/−120
• cbits/leveldb/db/dbformat.h +0/−215
• cbits/leveldb/db/dbformat_test.cc +0/−112
• cbits/leveldb/db/filename.cc +0/−139
• cbits/leveldb/db/filename.h +0/−80
• cbits/leveldb/db/filename_test.cc +0/−122
• cbits/leveldb/db/log_format.h +0/−35
• cbits/leveldb/db/log_reader.cc +0/−259
• cbits/leveldb/db/log_reader.h +0/−108
• cbits/leveldb/db/log_test.cc +0/−500
• cbits/leveldb/db/log_writer.cc +0/−103
• cbits/leveldb/db/log_writer.h +0/−48
• cbits/leveldb/db/memtable.cc +0/−145
• cbits/leveldb/db/memtable.h +0/−91
• cbits/leveldb/db/repair.cc +0/−387
• cbits/leveldb/db/skiplist.h +0/−378
• cbits/leveldb/db/skiplist_test.cc +0/−378
• cbits/leveldb/db/snapshot.h +0/−66
• cbits/leveldb/db/table_cache.cc +0/−95
• cbits/leveldb/db/table_cache.h +0/−50
• cbits/leveldb/db/version_edit.cc +0/−266
• cbits/leveldb/db/version_edit.h +0/−107
• cbits/leveldb/db/version_edit_test.cc +0/−46
• cbits/leveldb/db/version_set.cc +0/−1397
• cbits/leveldb/db/version_set.h +0/−370
• cbits/leveldb/db/version_set_test.cc +0/−179
• cbits/leveldb/db/write_batch.cc +0/−147
• cbits/leveldb/db/write_batch_internal.h +0/−49
• cbits/leveldb/db/write_batch_test.cc +0/−120
• cbits/leveldb/helpers/memenv/memenv.cc +0/−374
• cbits/leveldb/helpers/memenv/memenv.h +0/−20
• cbits/leveldb/helpers/memenv/memenv_test.cc +0/−232
• cbits/leveldb/include/leveldb/c.h +0/−246
• cbits/leveldb/include/leveldb/cache.h +0/−99
• cbits/leveldb/include/leveldb/comparator.h +0/−63
• cbits/leveldb/include/leveldb/db.h +0/−160
• cbits/leveldb/include/leveldb/env.h +0/−323
• cbits/leveldb/include/leveldb/iterator.h +0/−100
• cbits/leveldb/include/leveldb/options.h +0/−187
• cbits/leveldb/include/leveldb/slice.h +0/−109
• cbits/leveldb/include/leveldb/status.h +0/−100
• cbits/leveldb/include/leveldb/table.h +0/−70
• cbits/leveldb/include/leveldb/table_builder.h +0/−91
• cbits/leveldb/include/leveldb/write_batch.h +0/−64
• cbits/leveldb/port/atomic_pointer.h +0/−144
• cbits/leveldb/port/port.h +0/−21
• cbits/leveldb/port/port_android.cc +0/−64
• cbits/leveldb/port/port_android.h +0/−156
• cbits/leveldb/port/port_example.h +0/−125
• cbits/leveldb/port/port_posix.cc +0/−50
• cbits/leveldb/port/port_posix.h +0/−129
• cbits/leveldb/table/block.cc +0/−263
• cbits/leveldb/table/block.h +0/−43
• cbits/leveldb/table/block_builder.cc +0/−109
• cbits/leveldb/table/block_builder.h +0/−57
• cbits/leveldb/table/format.cc +0/−135
• cbits/leveldb/table/format.h +0/−103
• cbits/leveldb/table/iterator.cc +0/−67
• cbits/leveldb/table/iterator_wrapper.h +0/−63
• cbits/leveldb/table/merger.cc +0/−197
• cbits/leveldb/table/merger.h +0/−26
• cbits/leveldb/table/table.cc +0/−175
• cbits/leveldb/table/table_builder.cc +0/−227
• cbits/leveldb/table/table_test.cc +0/−854
• cbits/leveldb/table/two_level_iterator.cc +0/−182
• cbits/leveldb/table/two_level_iterator.h +0/−34
• cbits/leveldb/util/arena.cc +0/−68
• cbits/leveldb/util/arena.h +0/−68
• cbits/leveldb/util/arena_test.cc +0/−68
• cbits/leveldb/util/cache.cc +0/−328
• cbits/leveldb/util/cache_test.cc +0/−186
• cbits/leveldb/util/coding.cc +0/−194
• cbits/leveldb/util/coding.h +0/−104
• cbits/leveldb/util/coding_test.cc +0/−173
• cbits/leveldb/util/comparator.cc +0/−76
• cbits/leveldb/util/crc32c.cc +0/−332
• cbits/leveldb/util/crc32c.h +0/−45
• cbits/leveldb/util/crc32c_test.cc +0/−72
• cbits/leveldb/util/env.cc +0/−96
• cbits/leveldb/util/env_posix.cc +0/−567
• cbits/leveldb/util/env_test.cc +0/−104
• cbits/leveldb/util/hash.cc +0/−45
• cbits/leveldb/util/hash.h +0/−19
• cbits/leveldb/util/histogram.cc +0/−139
• cbits/leveldb/util/histogram.h +0/−42
• cbits/leveldb/util/logging.cc +0/−81
• cbits/leveldb/util/logging.h +0/−47
• cbits/leveldb/util/mutexlock.h +0/−39
• cbits/leveldb/util/options.cc +0/−28
• cbits/leveldb/util/posix_logger.h +0/−98
• cbits/leveldb/util/random.h +0/−59
• cbits/leveldb/util/status.cc +0/−75
• cbits/leveldb/util/testharness.cc +0/−77
• cbits/leveldb/util/testharness.h +0/−138
• cbits/leveldb/util/testutil.cc +0/−51
• cbits/leveldb/util/testutil.h +0/−53
• configure +0/−4104
• configure.ac +0/−64
• examples/comparator.hs +32/−0
• examples/features.hs +47/−27
• leveldb-haskell.buildinfo.in +0/−2
• leveldb-haskell.cabal +12/−73
• src/Database/LevelDB.hs +621/−266
• src/Database/LevelDB/Base.hsc +58/−58

@@ -1,16 +1,36 @@ This library provides Haskell bindings to [LevelDB](http://leveldb.googlecode.com) +## History++Version 0.1.0:++* memory (foreign pointers) is managed through+  [ResourceT](http://hackage.haskell.org/package/resourcet). Note that this+  requires to lift monadic actions inside the `MonadResource` monad, see the+  examples.+* links against shared library (LevelDB v1.3 or higher)+* LevelDB 1.3 API fully supported (including custom comparators, excluding+  custom environments)++Version 0.0.x:++* experimental releases+ ## Installation  Prerequisites:  * [GHC 7.*](http://www.haskell.org/ghc)-* [Cabal](http://www.haskell.org/cabal)+* [Cabal](http://www.haskell.org/cabal), version 1.3 or higher+* [LevelDB](http://code.google.com/p/leveldb) * Optional: [Snappy](http://code.google.com/p/snappy),   if compression support is desired-* Optional: `autoconf` +**Note:** as of version 1.3, LevelDB can be built as a shared library. Thus, as+of version 0.1.0 of this library, LevelDB is no longer bundled and must be+installed on the target system.+ To install the latest version from hackage:  ```shell@@ -20,7 +40,6 @@ To install from checked-out source:  ```shell-$ autoconf $ cabal install ``` 

@@ -1,2 +1,2 @@ import Distribution.Simple-main = defaultMainWithHooks autoconfUserHooks+main = defaultMain

@@ -1,88 +0,0 @@-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.-// Use of this source code is governed by a BSD-style license that can be-// found in the LICENSE file. See the AUTHORS file for names of contributors.--#include "db/builder.h"--#include "db/filename.h"-#include "db/dbformat.h"-#include "db/table_cache.h"-#include "db/version_edit.h"-#include "leveldb/db.h"-#include "leveldb/env.h"-#include "leveldb/iterator.h"--namespace leveldb {--Status BuildTable(const std::string& dbname,-                  Env* env,-                  const Options& options,-                  TableCache* table_cache,-                  Iterator* iter,-                  FileMetaData* meta) {-  Status s;-  meta->file_size = 0;-  iter->SeekToFirst();--  std::string fname = TableFileName(dbname, meta->number);-  if (iter->Valid()) {-    WritableFile* file;-    s = env->NewWritableFile(fname, &file);-    if (!s.ok()) {-      return s;-    }--    TableBuilder* builder = new TableBuilder(options, file);-    meta->smallest.DecodeFrom(iter->key());-    for (; iter->Valid(); iter->Next()) {-      Slice key = iter->key();-      meta->largest.DecodeFrom(key);-      builder->Add(key, iter->value());-    }--    // Finish and check for builder errors-    if (s.ok()) {-      s = builder->Finish();-      if (s.ok()) {-        meta->file_size = builder->FileSize();-        assert(meta->file_size > 0);-      }-    } else {-      builder->Abandon();-    }-    delete builder;--    // Finish and check for file errors-    if (s.ok()) {-      s = file->Sync();-    }-    if (s.ok()) {-      s = file->Close();-    }-    delete file;-    file = NULL;--    if (s.ok()) {-      // Verify that the table is usable-      Iterator* it = table_cache->NewIterator(ReadOptions(),-                                              meta->number,-                                              meta->file_size);-      s = it->status();-      delete it;-    }-  }--  // Check for input iterator errors-  if (!iter->status().ok()) {-    s = iter->status();-  }--  if (s.ok() && meta->file_size > 0) {-    // Keep it-  } else {-    env->DeleteFile(fname);-  }-  return s;-}--}  // namespace leveldb

@@ -1,34 +0,0 @@-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.-// Use of this source code is governed by a BSD-style license that can be-// found in the LICENSE file. See the AUTHORS file for names of contributors.--#ifndef STORAGE_LEVELDB_DB_BUILDER_H_-#define STORAGE_LEVELDB_DB_BUILDER_H_--#include "leveldb/status.h"--namespace leveldb {--struct Options;-struct FileMetaData;--class Env;-class Iterator;-class TableCache;-class VersionEdit;--// Build a Table file from the contents of *iter.  The generated file-// will be named according to meta->number.  On success, the rest of-// *meta will be filled with metadata about the generated table.-// If no data is present in *iter, meta->file_size will be set to-// zero, and no Table file will be produced.-extern Status BuildTable(const std::string& dbname,-                         Env* env,-                         const Options& options,-                         TableCache* table_cache,-                         Iterator* iter,-                         FileMetaData* meta);--}  // namespace leveldb--#endif  // STORAGE_LEVELDB_DB_BUILDER_H_

@@ -1,471 +0,0 @@-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.-// Use of this source code is governed by a BSD-style license that can be-// found in the LICENSE file. See the AUTHORS file for names of contributors.--#include "leveldb/c.h"--#include <stdlib.h>-#include <unistd.h>-#include "leveldb/cache.h"-#include "leveldb/comparator.h"-#include "leveldb/db.h"-#include "leveldb/env.h"-#include "leveldb/iterator.h"-#include "leveldb/options.h"-#include "leveldb/status.h"-#include "leveldb/write_batch.h"--using leveldb::Cache;-using leveldb::Comparator;-using leveldb::CompressionType;-using leveldb::DB;-using leveldb::Env;-using leveldb::FileLock;-using leveldb::Iterator;-using leveldb::Logger;-using leveldb::NewLRUCache;-using leveldb::Options;-using leveldb::RandomAccessFile;-using leveldb::Range;-using leveldb::ReadOptions;-using leveldb::SequentialFile;-using leveldb::Slice;-using leveldb::Snapshot;-using leveldb::Status;-using leveldb::WritableFile;-using leveldb::WriteBatch;-using leveldb::WriteOptions;--extern "C" {--struct leveldb_t              { DB*               rep; };-struct leveldb_iterator_t     { Iterator*         rep; };-struct leveldb_writebatch_t   { WriteBatch        rep; };-struct leveldb_snapshot_t     { const Snapshot*   rep; };-struct leveldb_readoptions_t  { ReadOptions       rep; };-struct leveldb_writeoptions_t { WriteOptions      rep; };-struct leveldb_options_t      { Options           rep; };-struct leveldb_cache_t        { Cache*            rep; };-struct leveldb_seqfile_t      { SequentialFile*   rep; };-struct leveldb_randomfile_t   { RandomAccessFile* rep; };-struct leveldb_writablefile_t { WritableFile*     rep; };-struct leveldb_logger_t       { Logger*           rep; };-struct leveldb_filelock_t     { FileLock*         rep; };--struct leveldb_comparator_t : public Comparator {-  void* state_;-  void (*destructor_)(void*);-  int (*compare_)(-      void*,-      const char* a, size_t alen,-      const char* b, size_t blen);-  const char* (*name_)(void*);--  virtual ~leveldb_comparator_t() {-    (*destructor_)(state_);-  }--  virtual int Compare(const Slice& a, const Slice& b) const {-    return (*compare_)(state_, a.data(), a.size(), b.data(), b.size());-  }--  virtual const char* Name() const {-    return (*name_)(state_);-  }--  // No-ops since the C binding does not support key shortening methods.-  virtual void FindShortestSeparator(std::string*, const Slice&) const { }-  virtual void FindShortSuccessor(std::string* key) const { }-};--struct leveldb_env_t {-  Env* rep;-  bool is_default;-};--static bool SaveError(char** errptr, const Status& s) {-  assert(errptr != NULL);-  if (s.ok()) {-    return false;-  } else if (*errptr == NULL) {-    *errptr = strdup(s.ToString().c_str());-  } else {-    // TODO(sanjay): Merge with existing error?-    free(*errptr);-    *errptr = strdup(s.ToString().c_str());-  }-  return true;-}--static char* CopyString(const std::string& str) {-  char* result = reinterpret_cast<char*>(malloc(sizeof(char) * str.size()));-  memcpy(result, str.data(), sizeof(char) * str.size());-  return result;-}--leveldb_t* leveldb_open(-    const leveldb_options_t* options,-    const char* name,-    char** errptr) {-  DB* db;-  if (SaveError(errptr, DB::Open(options->rep, std::string(name), &db))) {-    return NULL;-  }-  leveldb_t* result = new leveldb_t;-  result->rep = db;-  return result;-}--void leveldb_close(leveldb_t* db) {-  delete db->rep;-  delete db;-}--void leveldb_put(-    leveldb_t* db,-    const leveldb_writeoptions_t* options,-    const char* key, size_t keylen,-    const char* val, size_t vallen,-    char** errptr) {-  SaveError(errptr,-            db->rep->Put(options->rep, Slice(key, keylen), Slice(val, vallen)));-}--void leveldb_delete(-    leveldb_t* db,-    const leveldb_writeoptions_t* options,-    const char* key, size_t keylen,-    char** errptr) {-  SaveError(errptr, db->rep->Delete(options->rep, Slice(key, keylen)));-}---void leveldb_write(-    leveldb_t* db,-    const leveldb_writeoptions_t* options,-    leveldb_writebatch_t* batch,-    char** errptr) {-  SaveError(errptr, db->rep->Write(options->rep, &batch->rep));-}--char* leveldb_get(-    leveldb_t* db,-    const leveldb_readoptions_t* options,-    const char* key, size_t keylen,-    size_t* vallen,-    char** errptr) {-  char* result = NULL;-  std::string tmp;-  Status s = db->rep->Get(options->rep, Slice(key, keylen), &tmp);-  if (s.ok()) {-    *vallen = tmp.size();-    result = CopyString(tmp);-  } else {-    *vallen = 0;-    if (!s.IsNotFound()) {-      SaveError(errptr, s);-    }-  }-  return result;-}--leveldb_iterator_t* leveldb_create_iterator(-    leveldb_t* db,-    const leveldb_readoptions_t* options) {-  leveldb_iterator_t* result = new leveldb_iterator_t;-  result->rep = db->rep->NewIterator(options->rep);-  return result;-}--const leveldb_snapshot_t* leveldb_create_snapshot(-    leveldb_t* db) {-  leveldb_snapshot_t* result = new leveldb_snapshot_t;-  result->rep = db->rep->GetSnapshot();-  return result;-}--void leveldb_release_snapshot(-    leveldb_t* db,-    const leveldb_snapshot_t* snapshot) {-  db->rep->ReleaseSnapshot(snapshot->rep);-  delete snapshot;-}--char* leveldb_property_value(-    leveldb_t* db,-    const char* propname) {-  std::string tmp;-  if (db->rep->GetProperty(Slice(propname), &tmp)) {-    // We use strdup() since we expect human readable output.-    return strdup(tmp.c_str());-  } else {-    return NULL;-  }-}--void leveldb_approximate_sizes(-    leveldb_t* db,-    int num_ranges,-    const char* const* range_start_key, const size_t* range_start_key_len,-    const char* const* range_limit_key, const size_t* range_limit_key_len,-    uint64_t* sizes) {-  Range* ranges = new Range[num_ranges];-  for (int i = 0; i < num_ranges; i++) {-    ranges[i].start = Slice(range_start_key[i], range_start_key_len[i]);-    ranges[i].limit = Slice(range_limit_key[i], range_limit_key_len[i]);-  }-  db->rep->GetApproximateSizes(ranges, num_ranges, sizes);-  delete[] ranges;-}--void leveldb_destroy_db(-    const leveldb_options_t* options,-    const char* name,-    char** errptr) {-  SaveError(errptr, DestroyDB(name, options->rep));-}--void leveldb_repair_db(-    const leveldb_options_t* options,-    const char* name,-    char** errptr) {-  SaveError(errptr, RepairDB(name, options->rep));-}--void leveldb_iter_destroy(leveldb_iterator_t* iter) {-  delete iter->rep;-  delete iter;-}--unsigned char leveldb_iter_valid(const leveldb_iterator_t* iter) {-  return iter->rep->Valid();-}--void leveldb_iter_seek_to_first(leveldb_iterator_t* iter) {-  iter->rep->SeekToFirst();-}--void leveldb_iter_seek_to_last(leveldb_iterator_t* iter) {-  iter->rep->SeekToLast();-}--void leveldb_iter_seek(leveldb_iterator_t* iter, const char* k, size_t klen) {-  iter->rep->Seek(Slice(k, klen));-}--void leveldb_iter_next(leveldb_iterator_t* iter) {-  iter->rep->Next();-}--void leveldb_iter_prev(leveldb_iterator_t* iter) {-  iter->rep->Prev();-}--const char* leveldb_iter_key(const leveldb_iterator_t* iter, size_t* klen) {-  Slice s = iter->rep->key();-  *klen = s.size();-  return s.data();-}--const char* leveldb_iter_value(const leveldb_iterator_t* iter, size_t* vlen) {-  Slice s = iter->rep->value();-  *vlen = s.size();-  return s.data();-}--void leveldb_iter_get_error(const leveldb_iterator_t* iter, char** errptr) {-  SaveError(errptr, iter->rep->status());-}--leveldb_writebatch_t* leveldb_writebatch_create() {-  return new leveldb_writebatch_t;-}--void leveldb_writebatch_destroy(leveldb_writebatch_t* b) {-  delete b;-}--void leveldb_writebatch_clear(leveldb_writebatch_t* b) {-  b->rep.Clear();-}--void leveldb_writebatch_put(-    leveldb_writebatch_t* b,-    const char* key, size_t klen,-    const char* val, size_t vlen) {-  b->rep.Put(Slice(key, klen), Slice(val, vlen));-}--void leveldb_writebatch_delete(-    leveldb_writebatch_t* b,-    const char* key, size_t klen) {-  b->rep.Delete(Slice(key, klen));-}--void leveldb_writebatch_iterate(-    leveldb_writebatch_t* b,-    void* state,-    void (*put)(void*, const char* k, size_t klen, const char* v, size_t vlen),-    void (*deleted)(void*, const char* k, size_t klen)) {-  class H : public WriteBatch::Handler {-   public:-    void* state_;-    void (*put_)(void*, const char* k, size_t klen, const char* v, size_t vlen);-    void (*deleted_)(void*, const char* k, size_t klen);-    virtual void Put(const Slice& key, const Slice& value) {-      (*put_)(state_, key.data(), key.size(), value.data(), value.size());-    }-    virtual void Delete(const Slice& key) {-      (*deleted_)(state_, key.data(), key.size());-    }-  };-  H handler;-  handler.state_ = state;-  handler.put_ = put;-  handler.deleted_ = deleted;-  b->rep.Iterate(&handler);-}--leveldb_options_t* leveldb_options_create() {-  return new leveldb_options_t;-}--void leveldb_options_destroy(leveldb_options_t* options) {-  delete options;-}--void leveldb_options_set_comparator(-    leveldb_options_t* opt,-    leveldb_comparator_t* cmp) {-  opt->rep.comparator = cmp;-}--void leveldb_options_set_create_if_missing(-    leveldb_options_t* opt, unsigned char v) {-  opt->rep.create_if_missing = v;-}--void leveldb_options_set_error_if_exists(-    leveldb_options_t* opt, unsigned char v) {-  opt->rep.error_if_exists = v;-}--void leveldb_options_set_paranoid_checks(-    leveldb_options_t* opt, unsigned char v) {-  opt->rep.paranoid_checks = v;-}--void leveldb_options_set_env(leveldb_options_t* opt, leveldb_env_t* env) {-  opt->rep.env = (env ? env->rep : NULL);-}--void leveldb_options_set_info_log(leveldb_options_t* opt, leveldb_logger_t* l) {-  opt->rep.info_log = (l ? l->rep : NULL);-}--void leveldb_options_set_write_buffer_size(leveldb_options_t* opt, size_t s) {-  opt->rep.write_buffer_size = s;-}--void leveldb_options_set_max_open_files(leveldb_options_t* opt, int n) {-  opt->rep.max_open_files = n;-}--void leveldb_options_set_cache(leveldb_options_t* opt, leveldb_cache_t* c) {-  opt->rep.block_cache = c->rep;-}--void leveldb_options_set_block_size(leveldb_options_t* opt, size_t s) {-  opt->rep.block_size = s;-}--void leveldb_options_set_block_restart_interval(leveldb_options_t* opt, int n) {-  opt->rep.block_restart_interval = n;-}--void leveldb_options_set_compression(leveldb_options_t* opt, int t) {-  opt->rep.compression = static_cast<CompressionType>(t);-}--leveldb_comparator_t* leveldb_comparator_create(-    void* state,-    void (*destructor)(void*),-    int (*compare)(-        void*,-        const char* a, size_t alen,-        const char* b, size_t blen),-    const char* (*name)(void*)) {-  leveldb_comparator_t* result = new leveldb_comparator_t;-  result->state_ = state;-  result->destructor_ = destructor;-  result->compare_ = compare;-  result->name_ = name;-  return result;-}--void leveldb_comparator_destroy(leveldb_comparator_t* cmp) {-  delete cmp;-}--leveldb_readoptions_t* leveldb_readoptions_create() {-  return new leveldb_readoptions_t;-}--void leveldb_readoptions_destroy(leveldb_readoptions_t* opt) {-  delete opt;-}--void leveldb_readoptions_set_verify_checksums(-    leveldb_readoptions_t* opt,-    unsigned char v) {-  opt->rep.verify_checksums = v;-}--void leveldb_readoptions_set_fill_cache(-    leveldb_readoptions_t* opt, unsigned char v) {-  opt->rep.fill_cache = v;-}--void leveldb_readoptions_set_snapshot(-    leveldb_readoptions_t* opt,-    const leveldb_snapshot_t* snap) {-  opt->rep.snapshot = (snap ? snap->rep : NULL);-}--leveldb_writeoptions_t* leveldb_writeoptions_create() {-  return new leveldb_writeoptions_t;-}--void leveldb_writeoptions_destroy(leveldb_writeoptions_t* opt) {-  delete opt;-}--void leveldb_writeoptions_set_sync(-    leveldb_writeoptions_t* opt, unsigned char v) {-  opt->rep.sync = v;-}--leveldb_cache_t* leveldb_cache_create_lru(size_t capacity) {-  leveldb_cache_t* c = new leveldb_cache_t;-  c->rep = NewLRUCache(capacity);-  return c;-}--void leveldb_cache_destroy(leveldb_cache_t* cache) {-  delete cache->rep;-  delete cache;-}--leveldb_env_t* leveldb_create_default_env() {-  leveldb_env_t* result = new leveldb_env_t;-  result->rep = Env::Default();-  result->is_default = true;-  return result;-}--void leveldb_env_destroy(leveldb_env_t* env) {-  if (!env->is_default) delete env->rep;-  delete env;-}--}  // end extern "C"

@@ -1,359 +0,0 @@-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.-// Use of this source code is governed by a BSD-style license that can be-// found in the LICENSE file. See the AUTHORS file for names of contributors.--#include "leveldb/db.h"--#include <errno.h>-#include <fcntl.h>-#include <sys/stat.h>-#include <sys/types.h>-#include "leveldb/cache.h"-#include "leveldb/env.h"-#include "leveldb/table.h"-#include "leveldb/write_batch.h"-#include "db/db_impl.h"-#include "db/filename.h"-#include "db/log_format.h"-#include "db/version_set.h"-#include "util/logging.h"-#include "util/testharness.h"-#include "util/testutil.h"--namespace leveldb {--static const int kValueSize = 1000;--class CorruptionTest {- public:-  test::ErrorEnv env_;-  std::string dbname_;-  Cache* tiny_cache_;-  Options options_;-  DB* db_;--  CorruptionTest() {-    tiny_cache_ = NewLRUCache(100);-    options_.env = &env_;-    dbname_ = test::TmpDir() + "/db_test";-    DestroyDB(dbname_, options_);--    db_ = NULL;-    options_.create_if_missing = true;-    Reopen();-    options_.create_if_missing = false;-  }--  ~CorruptionTest() {-     delete db_;-     DestroyDB(dbname_, Options());-     delete tiny_cache_;-  }--  Status TryReopen(Options* options = NULL) {-    delete db_;-    db_ = NULL;-    Options opt = (options ? *options : options_);-    opt.env = &env_;-    opt.block_cache = tiny_cache_;-    return DB::Open(opt, dbname_, &db_);-  }--  void Reopen(Options* options = NULL) {-    ASSERT_OK(TryReopen(options));-  }--  void RepairDB() {-    delete db_;-    db_ = NULL;-    ASSERT_OK(::leveldb::RepairDB(dbname_, options_));-  }--  void Build(int n) {-    std::string key_space, value_space;-    WriteBatch batch;-    for (int i = 0; i < n; i++) {-      //if ((i % 100) == 0) fprintf(stderr, "@ %d of %d\n", i, n);-      Slice key = Key(i, &key_space);-      batch.Clear();-      batch.Put(key, Value(i, &value_space));-      ASSERT_OK(db_->Write(WriteOptions(), &batch));-    }-  }--  void Check(int min_expected, int max_expected) {-    int next_expected = 0;-    int missed = 0;-    int bad_keys = 0;-    int bad_values = 0;-    int correct = 0;-    std::string value_space;-    Iterator* iter = db_->NewIterator(ReadOptions());-    for (iter->SeekToFirst(); iter->Valid(); iter->Next()) {-      uint64_t key;-      Slice in(iter->key());-      if (!ConsumeDecimalNumber(&in, &key) ||-          !in.empty() ||-          key < next_expected) {-        bad_keys++;-        continue;-      }-      missed += (key - next_expected);-      next_expected = key + 1;-      if (iter->value() != Value(key, &value_space)) {-        bad_values++;-      } else {-        correct++;-      }-    }-    delete iter;--    fprintf(stderr,-            "expected=%d..%d; got=%d; bad_keys=%d; bad_values=%d; missed=%d\n",-            min_expected, max_expected, correct, bad_keys, bad_values, missed);-    ASSERT_LE(min_expected, correct);-    ASSERT_GE(max_expected, correct);-  }--  void Corrupt(FileType filetype, int offset, int bytes_to_corrupt) {-    // Pick file to corrupt-    std::vector<std::string> filenames;-    ASSERT_OK(env_.GetChildren(dbname_, &filenames));-    uint64_t number;-    FileType type;-    std::string fname;-    int picked_number = -1;-    for (int i = 0; i < filenames.size(); i++) {-      if (ParseFileName(filenames[i], &number, &type) &&-          type == filetype &&-          int(number) > picked_number) {  // Pick latest file-        fname = dbname_ + "/" + filenames[i];-        picked_number = number;-      }-    }-    ASSERT_TRUE(!fname.empty()) << filetype;--    struct stat sbuf;-    if (stat(fname.c_str(), &sbuf) != 0) {-      const char* msg = strerror(errno);-      ASSERT_TRUE(false) << fname << ": " << msg;-    }--    if (offset < 0) {-      // Relative to end of file; make it absolute-      if (-offset > sbuf.st_size) {-        offset = 0;-      } else {-        offset = sbuf.st_size + offset;-      }-    }-    if (offset > sbuf.st_size) {-      offset = sbuf.st_size;-    }-    if (offset + bytes_to_corrupt > sbuf.st_size) {-      bytes_to_corrupt = sbuf.st_size - offset;-    }--    // Do it-    std::string contents;-    Status s = ReadFileToString(Env::Default(), fname, &contents);-    ASSERT_TRUE(s.ok()) << s.ToString();-    for (int i = 0; i < bytes_to_corrupt; i++) {-      contents[i + offset] ^= 0x80;-    }-    s = WriteStringToFile(Env::Default(), contents, fname);-    ASSERT_TRUE(s.ok()) << s.ToString();-  }--  int Property(const std::string& name) {-    std::string property;-    int result;-    if (db_->GetProperty(name, &property) &&-        sscanf(property.c_str(), "%d", &result) == 1) {-      return result;-    } else {-      return -1;-    }-  }--  // Return the ith key-  Slice Key(int i, std::string* storage) {-    char buf[100];-    snprintf(buf, sizeof(buf), "%016d", i);-    storage->assign(buf, strlen(buf));-    return Slice(*storage);-  }--  // Return the value to associate with the specified key-  Slice Value(int k, std::string* storage) {-    Random r(k);-    return test::RandomString(&r, kValueSize, storage);-  }-};--TEST(CorruptionTest, Recovery) {-  Build(100);-  Check(100, 100);-  Corrupt(kLogFile, 19, 1);      // WriteBatch tag for first record-  Corrupt(kLogFile, log::kBlockSize + 1000, 1);  // Somewhere in second block-  Reopen();--  // The 64 records in the first two log blocks are completely lost.-  Check(36, 36);-}--TEST(CorruptionTest, RecoverWriteError) {-  env_.writable_file_error_ = true;-  Status s = TryReopen();-  ASSERT_TRUE(!s.ok());-}--TEST(CorruptionTest, NewFileErrorDuringWrite) {-  // Do enough writing to force minor compaction-  env_.writable_file_error_ = true;-  const int num = 3 + (Options().write_buffer_size / kValueSize);-  std::string value_storage;-  Status s;-  for (int i = 0; s.ok() && i < num; i++) {-    WriteBatch batch;-    batch.Put("a", Value(100, &value_storage));-    s = db_->Write(WriteOptions(), &batch);-  }-  ASSERT_TRUE(!s.ok());-  ASSERT_GE(env_.num_writable_file_errors_, 1);-  env_.writable_file_error_ = false;-  Reopen();-}--TEST(CorruptionTest, TableFile) {-  Build(100);-  DBImpl* dbi = reinterpret_cast<DBImpl*>(db_);-  dbi->TEST_CompactMemTable();-  dbi->TEST_CompactRange(0, NULL, NULL);-  dbi->TEST_CompactRange(1, NULL, NULL);--  Corrupt(kTableFile, 100, 1);-  Check(99, 99);-}--TEST(CorruptionTest, TableFileIndexData) {-  Build(10000);  // Enough to build multiple Tables-  DBImpl* dbi = reinterpret_cast<DBImpl*>(db_);-  dbi->TEST_CompactMemTable();--  Corrupt(kTableFile, -2000, 500);-  Reopen();-  Check(5000, 9999);-}--TEST(CorruptionTest, MissingDescriptor) {-  Build(1000);-  RepairDB();-  Reopen();-  Check(1000, 1000);-}--TEST(CorruptionTest, SequenceNumberRecovery) {-  ASSERT_OK(db_->Put(WriteOptions(), "foo", "v1"));-  ASSERT_OK(db_->Put(WriteOptions(), "foo", "v2"));-  ASSERT_OK(db_->Put(WriteOptions(), "foo", "v3"));-  ASSERT_OK(db_->Put(WriteOptions(), "foo", "v4"));-  ASSERT_OK(db_->Put(WriteOptions(), "foo", "v5"));-  RepairDB();-  Reopen();-  std::string v;-  ASSERT_OK(db_->Get(ReadOptions(), "foo", &v));-  ASSERT_EQ("v5", v);-  // Write something.  If sequence number was not recovered properly,-  // it will be hidden by an earlier write.-  ASSERT_OK(db_->Put(WriteOptions(), "foo", "v6"));-  ASSERT_OK(db_->Get(ReadOptions(), "foo", &v));-  ASSERT_EQ("v6", v);-  Reopen();-  ASSERT_OK(db_->Get(ReadOptions(), "foo", &v));-  ASSERT_EQ("v6", v);-}--TEST(CorruptionTest, CorruptedDescriptor) {-  ASSERT_OK(db_->Put(WriteOptions(), "foo", "hello"));-  DBImpl* dbi = reinterpret_cast<DBImpl*>(db_);-  dbi->TEST_CompactMemTable();-  dbi->TEST_CompactRange(0, NULL, NULL);--  Corrupt(kDescriptorFile, 0, 1000);-  Status s = TryReopen();-  ASSERT_TRUE(!s.ok());--  RepairDB();-  Reopen();-  std::string v;-  ASSERT_OK(db_->Get(ReadOptions(), "foo", &v));-  ASSERT_EQ("hello", v);-}--TEST(CorruptionTest, CompactionInputError) {-  Build(10);-  DBImpl* dbi = reinterpret_cast<DBImpl*>(db_);-  dbi->TEST_CompactMemTable();-  const int last = config::kMaxMemCompactLevel;-  ASSERT_EQ(1, Property("leveldb.num-files-at-level" + NumberToString(last)));--  Corrupt(kTableFile, 100, 1);-  Check(9, 9);--  // Force compactions by writing lots of values-  Build(10000);-  Check(10000, 10000);-}--TEST(CorruptionTest, CompactionInputErrorParanoid) {-  Options options;-  options.paranoid_checks = true;-  options.write_buffer_size = 1048576;-  Reopen(&options);-  DBImpl* dbi = reinterpret_cast<DBImpl*>(db_);--  // Fill levels >= 1 so memtable compaction outputs to level 1-  for (int level = 1; level < config::kNumLevels; level++) {-    dbi->Put(WriteOptions(), "", "begin");-    dbi->Put(WriteOptions(), "~", "end");-    dbi->TEST_CompactMemTable();-  }--  Build(10);-  dbi->TEST_CompactMemTable();-  ASSERT_EQ(1, Property("leveldb.num-files-at-level0"));--  Corrupt(kTableFile, 100, 1);-  Check(9, 9);--  // Write must eventually fail because of corrupted table-  Status s;-  std::string tmp1, tmp2;-  for (int i = 0; i < 10000 && s.ok(); i++) {-    s = db_->Put(WriteOptions(), Key(i, &tmp1), Value(i, &tmp2));-  }-  ASSERT_TRUE(!s.ok()) << "write did not fail in corrupted paranoid db";-}--TEST(CorruptionTest, UnrelatedKeys) {-  Build(10);-  DBImpl* dbi = reinterpret_cast<DBImpl*>(db_);-  dbi->TEST_CompactMemTable();-  Corrupt(kTableFile, 100, 1);--  std::string tmp1, tmp2;-  ASSERT_OK(db_->Put(WriteOptions(), Key(1000, &tmp1), Value(1000, &tmp2)));-  std::string v;-  ASSERT_OK(db_->Get(ReadOptions(), Key(1000, &tmp1), &v));-  ASSERT_EQ(Value(1000, &tmp2).ToString(), v);-  dbi->TEST_CompactMemTable();-  ASSERT_OK(db_->Get(ReadOptions(), Key(1000, &tmp1), &v));-  ASSERT_EQ(Value(1000, &tmp2).ToString(), v);-}--}  // namespace leveldb--int main(int argc, char** argv) {-  return leveldb::test::RunAllTests();-}

@@ -1,877 +0,0 @@-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.-// Use of this source code is governed by a BSD-style license that can be-// found in the LICENSE file. See the AUTHORS file for names of contributors.--#include <sys/types.h>-#include <stdio.h>-#include <stdlib.h>-#include "db/db_impl.h"-#include "db/version_set.h"-#include "leveldb/cache.h"-#include "leveldb/db.h"-#include "leveldb/env.h"-#include "leveldb/write_batch.h"-#include "port/port.h"-#include "util/crc32c.h"-#include "util/histogram.h"-#include "util/mutexlock.h"-#include "util/random.h"-#include "util/testutil.h"--// Comma-separated list of operations to run in the specified order-//   Actual benchmarks:-//      fillseq       -- write N values in sequential key order in async mode-//      fillrandom    -- write N values in random key order in async mode-//      overwrite     -- overwrite N values in random key order in async mode-//      fillsync      -- write N/100 values in random key order in sync mode-//      fill100K      -- write N/1000 100K values in random order in async mode-//      readseq       -- read N times sequentially-//      readreverse   -- read N times in reverse order-//      readrandom    -- read N times in random order-//      readhot       -- read N times in random order from 1% section of DB-//      crc32c        -- repeated crc32c of 4K of data-//      acquireload   -- load N*1000 times-//   Meta operations:-//      compact     -- Compact the entire DB-//      stats       -- Print DB stats-//      heapprofile -- Dump a heap profile (if supported by this port)-static const char* FLAGS_benchmarks =-    "fillseq,"-    "fillsync,"-    "fillrandom,"-    "overwrite,"-    "readrandom,"-    "readrandom,"  // Extra run to allow previous compactions to quiesce-    "readseq,"-    "readreverse,"-    "compact,"-    "readrandom,"-    "readseq,"-    "readreverse,"-    "fill100K,"-    "crc32c,"-    "snappycomp,"-    "snappyuncomp,"-    "acquireload,"-    ;--// Number of key/values to place in database-static int FLAGS_num = 1000000;--// Number of read operations to do.  If negative, do FLAGS_num reads.-static int FLAGS_reads = -1;--// Number of concurrent threads to run.-static int FLAGS_threads = 1;--// Size of each value-static int FLAGS_value_size = 100;--// Arrange to generate values that shrink to this fraction of-// their original size after compression-static double FLAGS_compression_ratio = 0.5;--// Print histogram of operation timings-static bool FLAGS_histogram = false;--// Number of bytes to buffer in memtable before compacting-// (initialized to default value by "main")-static int FLAGS_write_buffer_size = 0;--// Number of bytes to use as a cache of uncompressed data.-// Negative means use default settings.-static int FLAGS_cache_size = -1;--// Maximum number of files to keep open at the same time (use default if == 0)-static int FLAGS_open_files = 0;--// If true, do not destroy the existing database.  If you set this-// flag and also specify a benchmark that wants a fresh database, that-// benchmark will fail.-static bool FLAGS_use_existing_db = false;--// Use the db with the following name.-static const char* FLAGS_db = "/tmp/dbbench";--namespace leveldb {--namespace {--// Helper for quickly generating random data.-class RandomGenerator {- private:-  std::string data_;-  int pos_;-- public:-  RandomGenerator() {-    // We use a limited amount of data over and over again and ensure-    // that it is larger than the compression window (32KB), and also-    // large enough to serve all typical value sizes we want to write.-    Random rnd(301);-    std::string piece;-    while (data_.size() < 1048576) {-      // Add a short fragment that is as compressible as specified-      // by FLAGS_compression_ratio.-      test::CompressibleString(&rnd, FLAGS_compression_ratio, 100, &piece);-      data_.append(piece);-    }-    pos_ = 0;-  }--  Slice Generate(int len) {-    if (pos_ + len > data_.size()) {-      pos_ = 0;-      assert(len < data_.size());-    }-    pos_ += len;-    return Slice(data_.data() + pos_ - len, len);-  }-};--static Slice TrimSpace(Slice s) {-  int start = 0;-  while (start < s.size() && isspace(s[start])) {-    start++;-  }-  int limit = s.size();-  while (limit > start && isspace(s[limit-1])) {-    limit--;-  }-  return Slice(s.data() + start, limit - start);-}--static void AppendWithSpace(std::string* str, Slice msg) {-  if (msg.empty()) return;-  if (!str->empty()) {-    str->push_back(' ');-  }-  str->append(msg.data(), msg.size());-}--class Stats {- private:-  double start_;-  double finish_;-  double seconds_;-  int done_;-  int next_report_;-  int64_t bytes_;-  double last_op_finish_;-  Histogram hist_;-  std::string message_;-- public:-  Stats() { Start(); }--  void Start() {-    next_report_ = 100;-    last_op_finish_ = start_;-    hist_.Clear();-    done_ = 0;-    bytes_ = 0;-    seconds_ = 0;-    start_ = Env::Default()->NowMicros();-    finish_ = start_;-    message_.clear();-  }--  void Merge(const Stats& other) {-    hist_.Merge(other.hist_);-    done_ += other.done_;-    bytes_ += other.bytes_;-    seconds_ += other.seconds_;-    if (other.start_ < start_) start_ = other.start_;-    if (other.finish_ > finish_) finish_ = other.finish_;--    // Just keep the messages from one thread-    if (message_.empty()) message_ = other.message_;-  }--  void Stop() {-    finish_ = Env::Default()->NowMicros();-    seconds_ = (finish_ - start_) * 1e-6;-  }--  void AddMessage(Slice msg) {-    AppendWithSpace(&message_, msg);-  }--  void FinishedSingleOp() {-    if (FLAGS_histogram) {-      double now = Env::Default()->NowMicros();-      double micros = now - last_op_finish_;-      hist_.Add(micros);-      if (micros > 20000) {-        fprintf(stderr, "long op: %.1f micros%30s\r", micros, "");-        fflush(stderr);-      }-      last_op_finish_ = now;-    }--    done_++;-    if (done_ >= next_report_) {-      if      (next_report_ < 1000)   next_report_ += 100;-      else if (next_report_ < 5000)   next_report_ += 500;-      else if (next_report_ < 10000)  next_report_ += 1000;-      else if (next_report_ < 50000)  next_report_ += 5000;-      else if (next_report_ < 100000) next_report_ += 10000;-      else if (next_report_ < 500000) next_report_ += 50000;-      else                            next_report_ += 100000;-      fprintf(stderr, "... finished %d ops%30s\r", done_, "");-      fflush(stderr);-    }-  }--  void AddBytes(int64_t n) {-    bytes_ += n;-  }--  void Report(const Slice& name) {-    // Pretend at least one op was done in case we are running a benchmark-    // that does not call FinishedSingleOp().-    if (done_ < 1) done_ = 1;--    std::string extra;-    if (bytes_ > 0) {-      // Rate is computed on actual elapsed time, not the sum of per-thread-      // elapsed times.-      double elapsed = (finish_ - start_) * 1e-6;-      char rate[100];-      snprintf(rate, sizeof(rate), "%6.1f MB/s",-               (bytes_ / 1048576.0) / elapsed);-      extra = rate;-    }-    AppendWithSpace(&extra, message_);--    fprintf(stdout, "%-12s : %11.3f micros/op;%s%s\n",-            name.ToString().c_str(),-            seconds_ * 1e6 / done_,-            (extra.empty() ? "" : " "),-            extra.c_str());-    if (FLAGS_histogram) {-      fprintf(stdout, "Microseconds per op:\n%s\n", hist_.ToString().c_str());-    }-    fflush(stdout);-  }-};--// State shared by all concurrent executions of the same benchmark.-struct SharedState {-  port::Mutex mu;-  port::CondVar cv;-  int total;--  // Each thread goes through the following states:-  //    (1) initializing-  //    (2) waiting for others to be initialized-  //    (3) running-  //    (4) done--  int num_initialized;-  int num_done;-  bool start;--  SharedState() : cv(&mu) { }-};--// Per-thread state for concurrent executions of the same benchmark.-struct ThreadState {-  int tid;             // 0..n-1 when running in n threads-  Random rand;         // Has different seeds for different threads-  Stats stats;-  SharedState* shared;--  ThreadState(int index)-      : tid(index),-        rand(1000 + index) {-  }-};--}  // namespace--class Benchmark {- private:-  Cache* cache_;-  DB* db_;-  int num_;-  int value_size_;-  int entries_per_batch_;-  WriteOptions write_options_;-  int reads_;-  int heap_counter_;--  void PrintHeader() {-    const int kKeySize = 16;-    PrintEnvironment();-    fprintf(stdout, "Keys:       %d bytes each\n", kKeySize);-    fprintf(stdout, "Values:     %d bytes each (%d bytes after compression)\n",-            FLAGS_value_size,-            static_cast<int>(FLAGS_value_size * FLAGS_compression_ratio + 0.5));-    fprintf(stdout, "Entries:    %d\n", num_);-    fprintf(stdout, "RawSize:    %.1f MB (estimated)\n",-            ((static_cast<int64_t>(kKeySize + FLAGS_value_size) * num_)-             / 1048576.0));-    fprintf(stdout, "FileSize:   %.1f MB (estimated)\n",-            (((kKeySize + FLAGS_value_size * FLAGS_compression_ratio) * num_)-             / 1048576.0));-    PrintWarnings();-    fprintf(stdout, "------------------------------------------------\n");-  }--  void PrintWarnings() {-#if defined(__GNUC__) && !defined(__OPTIMIZE__)-    fprintf(stdout,-            "WARNING: Optimization is disabled: benchmarks unnecessarily slow\n"-            );-#endif-#ifndef NDEBUG-    fprintf(stdout,-            "WARNING: Assertions are enabled; benchmarks unnecessarily slow\n");-#endif--    // See if snappy is working by attempting to compress a compressible string-    const char text[] = "yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy";-    std::string compressed;-    if (!port::Snappy_Compress(text, sizeof(text), &compressed)) {-      fprintf(stdout, "WARNING: Snappy compression is not enabled\n");-    } else if (compressed.size() >= sizeof(text)) {-      fprintf(stdout, "WARNING: Snappy compression is not effective\n");-    }-  }--  void PrintEnvironment() {-    fprintf(stderr, "LevelDB:    version %d.%d\n",-            kMajorVersion, kMinorVersion);--#if defined(__linux)-    time_t now = time(NULL);-    fprintf(stderr, "Date:       %s", ctime(&now));  // ctime() adds newline--    FILE* cpuinfo = fopen("/proc/cpuinfo", "r");-    if (cpuinfo != NULL) {-      char line[1000];-      int num_cpus = 0;-      std::string cpu_type;-      std::string cache_size;-      while (fgets(line, sizeof(line), cpuinfo) != NULL) {-        const char* sep = strchr(line, ':');-        if (sep == NULL) {-          continue;-        }-        Slice key = TrimSpace(Slice(line, sep - 1 - line));-        Slice val = TrimSpace(Slice(sep + 1));-        if (key == "model name") {-          ++num_cpus;-          cpu_type = val.ToString();-        } else if (key == "cache size") {-          cache_size = val.ToString();-        }-      }-      fclose(cpuinfo);-      fprintf(stderr, "CPU:        %d * %s\n", num_cpus, cpu_type.c_str());-      fprintf(stderr, "CPUCache:   %s\n", cache_size.c_str());-    }-#endif-  }-- public:-  Benchmark()-  : cache_(FLAGS_cache_size >= 0 ? NewLRUCache(FLAGS_cache_size) : NULL),-    db_(NULL),-    num_(FLAGS_num),-    value_size_(FLAGS_value_size),-    entries_per_batch_(1),-    reads_(FLAGS_reads < 0 ? FLAGS_num : FLAGS_reads),-    heap_counter_(0) {-    std::vector<std::string> files;-    Env::Default()->GetChildren(FLAGS_db, &files);-    for (int i = 0; i < files.size(); i++) {-      if (Slice(files[i]).starts_with("heap-")) {-        Env::Default()->DeleteFile(std::string(FLAGS_db) + "/" + files[i]);-      }-    }-    if (!FLAGS_use_existing_db) {-      DestroyDB(FLAGS_db, Options());-    }-  }--  ~Benchmark() {-    delete db_;-    delete cache_;-  }--  void Run() {-    PrintHeader();-    Open();--    const char* benchmarks = FLAGS_benchmarks;-    while (benchmarks != NULL) {-      const char* sep = strchr(benchmarks, ',');-      Slice name;-      if (sep == NULL) {-        name = benchmarks;-        benchmarks = NULL;-      } else {-        name = Slice(benchmarks, sep - benchmarks);-        benchmarks = sep + 1;-      }--      // Reset parameters that may be overriddden bwlow-      num_ = FLAGS_num;-      reads_ = (FLAGS_reads < 0 ? FLAGS_num : FLAGS_reads);-      value_size_ = FLAGS_value_size;-      entries_per_batch_ = 1;-      write_options_ = WriteOptions();--      void (Benchmark::*method)(ThreadState*) = NULL;-      bool fresh_db = false;-      int num_threads = FLAGS_threads;--      if (name == Slice("fillseq")) {-        fresh_db = true;-        method = &Benchmark::WriteSeq;-      } else if (name == Slice("fillbatch")) {-        fresh_db = true;-        entries_per_batch_ = 1000;-        method = &Benchmark::WriteSeq;-      } else if (name == Slice("fillrandom")) {-        fresh_db = true;-        method = &Benchmark::WriteRandom;-      } else if (name == Slice("overwrite")) {-        fresh_db = false;-        method = &Benchmark::WriteRandom;-      } else if (name == Slice("fillsync")) {-        fresh_db = true;-        num_ /= 1000;-        write_options_.sync = true;-        method = &Benchmark::WriteRandom;-      } else if (name == Slice("fill100K")) {-        fresh_db = true;-        num_ /= 1000;-        value_size_ = 100 * 1000;-        method = &Benchmark::WriteRandom;-      } else if (name == Slice("readseq")) {-        method = &Benchmark::ReadSequential;-      } else if (name == Slice("readreverse")) {-        method = &Benchmark::ReadReverse;-      } else if (name == Slice("readrandom")) {-        method = &Benchmark::ReadRandom;-      } else if (name == Slice("readhot")) {-        method = &Benchmark::ReadHot;-      } else if (name == Slice("readrandomsmall")) {-        reads_ /= 1000;-        method = &Benchmark::ReadRandom;-      } else if (name == Slice("readwhilewriting")) {-        num_threads++;  // Add extra thread for writing-        method = &Benchmark::ReadWhileWriting;-      } else if (name == Slice("compact")) {-        method = &Benchmark::Compact;-      } else if (name == Slice("crc32c")) {-        method = &Benchmark::Crc32c;-      } else if (name == Slice("acquireload")) {-        method = &Benchmark::AcquireLoad;-      } else if (name == Slice("snappycomp")) {-        method = &Benchmark::SnappyCompress;-      } else if (name == Slice("snappyuncomp")) {-        method = &Benchmark::SnappyUncompress;-      } else if (name == Slice("heapprofile")) {-        HeapProfile();-      } else if (name == Slice("stats")) {-        PrintStats();-      } else {-        if (name != Slice()) {  // No error message for empty name-          fprintf(stderr, "unknown benchmark '%s'\n", name.ToString().c_str());-        }-      }--      if (fresh_db) {-        if (FLAGS_use_existing_db) {-          fprintf(stdout, "%-12s : skipped (--use_existing_db is true)\n",-                  name.ToString().c_str());-          method = NULL;-        } else {-          delete db_;-          db_ = NULL;-          DestroyDB(FLAGS_db, Options());-          Open();-        }-      }--      if (method != NULL) {-        RunBenchmark(num_threads, name, method);-      }-    }-  }-- private:-  struct ThreadArg {-    Benchmark* bm;-    SharedState* shared;-    ThreadState* thread;-    void (Benchmark::*method)(ThreadState*);-  };--  static void ThreadBody(void* v) {-    ThreadArg* arg = reinterpret_cast<ThreadArg*>(v);-    SharedState* shared = arg->shared;-    ThreadState* thread = arg->thread;-    {-      MutexLock l(&shared->mu);-      shared->num_initialized++;-      if (shared->num_initialized >= shared->total) {-        shared->cv.SignalAll();-      }-      while (!shared->start) {-        shared->cv.Wait();-      }-    }--    thread->stats.Start();-    (arg->bm->*(arg->method))(thread);-    thread->stats.Stop();--    {-      MutexLock l(&shared->mu);-      shared->num_done++;-      if (shared->num_done >= shared->total) {-        shared->cv.SignalAll();-      }-    }-  }--  void RunBenchmark(int n, Slice name,-                    void (Benchmark::*method)(ThreadState*)) {-    SharedState shared;-    shared.total = n;-    shared.num_initialized = 0;-    shared.num_done = 0;-    shared.start = false;--    ThreadArg* arg = new ThreadArg[n];-    for (int i = 0; i < n; i++) {-      arg[i].bm = this;-      arg[i].method = method;-      arg[i].shared = &shared;-      arg[i].thread = new ThreadState(i);-      arg[i].thread->shared = &shared;-      Env::Default()->StartThread(ThreadBody, &arg[i]);-    }--    shared.mu.Lock();-    while (shared.num_initialized < n) {-      shared.cv.Wait();-    }--    shared.start = true;-    shared.cv.SignalAll();-    while (shared.num_done < n) {-      shared.cv.Wait();-    }-    shared.mu.Unlock();--    for (int i = 1; i < n; i++) {-      arg[0].thread->stats.Merge(arg[i].thread->stats);-    }-    arg[0].thread->stats.Report(name);--    for (int i = 0; i < n; i++) {-      delete arg[i].thread;-    }-    delete[] arg;-  }--  void Crc32c(ThreadState* thread) {-    // Checksum about 500MB of data total-    const int size = 4096;-    const char* label = "(4K per op)";-    std::string data(size, 'x');-    int64_t bytes = 0;-    uint32_t crc = 0;-    while (bytes < 500 * 1048576) {-      crc = crc32c::Value(data.data(), size);-      thread->stats.FinishedSingleOp();-      bytes += size;-    }-    // Print so result is not dead-    fprintf(stderr, "... crc=0x%x\r", static_cast<unsigned int>(crc));--    thread->stats.AddBytes(bytes);-    thread->stats.AddMessage(label);-  }--  void AcquireLoad(ThreadState* thread) {-    int dummy;-    port::AtomicPointer ap(&dummy);-    int count = 0;-    void *ptr = NULL;-    thread->stats.AddMessage("(each op is 1000 loads)");-    while (count < 100000) {-      for (int i = 0; i < 1000; i++) {-        ptr = ap.Acquire_Load();-      }-      count++;-      thread->stats.FinishedSingleOp();-    }-    if (ptr == NULL) exit(1); // Disable unused variable warning.-  }--  void SnappyCompress(ThreadState* thread) {-    RandomGenerator gen;-    Slice input = gen.Generate(Options().block_size);-    int64_t bytes = 0;-    int64_t produced = 0;-    bool ok = true;-    std::string compressed;-    while (ok && bytes < 1024 * 1048576) {  // Compress 1G-      ok = port::Snappy_Compress(input.data(), input.size(), &compressed);-      produced += compressed.size();-      bytes += input.size();-      thread->stats.FinishedSingleOp();-    }--    if (!ok) {-      thread->stats.AddMessage("(snappy failure)");-    } else {-      char buf[100];-      snprintf(buf, sizeof(buf), "(output: %.1f%%)",-               (produced * 100.0) / bytes);-      thread->stats.AddMessage(buf);-      thread->stats.AddBytes(bytes);-    }-  }--  void SnappyUncompress(ThreadState* thread) {-    RandomGenerator gen;-    Slice input = gen.Generate(Options().block_size);-    std::string compressed;-    bool ok = port::Snappy_Compress(input.data(), input.size(), &compressed);-    int64_t bytes = 0;-    char* uncompressed = new char[input.size()];-    while (ok && bytes < 1024 * 1048576) {  // Compress 1G-      ok =  port::Snappy_Uncompress(compressed.data(), compressed.size(),-                                    uncompressed);-      bytes += input.size();-      thread->stats.FinishedSingleOp();-    }-    delete[] uncompressed;--    if (!ok) {-      thread->stats.AddMessage("(snappy failure)");-    } else {-      thread->stats.AddBytes(bytes);-    }-  }--  void Open() {-    assert(db_ == NULL);-    Options options;-    options.create_if_missing = !FLAGS_use_existing_db;-    options.block_cache = cache_;-    options.write_buffer_size = FLAGS_write_buffer_size;-    Status s = DB::Open(options, FLAGS_db, &db_);-    if (!s.ok()) {-      fprintf(stderr, "open error: %s\n", s.ToString().c_str());-      exit(1);-    }-  }--  void WriteSeq(ThreadState* thread) {-    DoWrite(thread, true);-  }--  void WriteRandom(ThreadState* thread) {-    DoWrite(thread, false);-  }--  void DoWrite(ThreadState* thread, bool seq) {-    if (num_ != FLAGS_num) {-      char msg[100];-      snprintf(msg, sizeof(msg), "(%d ops)", num_);-      thread->stats.AddMessage(msg);-    }--    RandomGenerator gen;-    WriteBatch batch;-    Status s;-    int64_t bytes = 0;-    for (int i = 0; i < num_; i += entries_per_batch_) {-      batch.Clear();-      for (int j = 0; j < entries_per_batch_; j++) {-        const int k = seq ? i+j : (thread->rand.Next() % FLAGS_num);-        char key[100];-        snprintf(key, sizeof(key), "%016d", k);-        batch.Put(key, gen.Generate(value_size_));-        bytes += value_size_ + strlen(key);-        thread->stats.FinishedSingleOp();-      }-      s = db_->Write(write_options_, &batch);-      if (!s.ok()) {-        fprintf(stderr, "put error: %s\n", s.ToString().c_str());-        exit(1);-      }-    }-    thread->stats.AddBytes(bytes);-  }--  void ReadSequential(ThreadState* thread) {-    Iterator* iter = db_->NewIterator(ReadOptions());-    int i = 0;-    int64_t bytes = 0;-    for (iter->SeekToFirst(); i < reads_ && iter->Valid(); iter->Next()) {-      bytes += iter->key().size() + iter->value().size();-      thread->stats.FinishedSingleOp();-      ++i;-    }-    delete iter;-    thread->stats.AddBytes(bytes);-  }--  void ReadReverse(ThreadState* thread) {-    Iterator* iter = db_->NewIterator(ReadOptions());-    int i = 0;-    int64_t bytes = 0;-    for (iter->SeekToLast(); i < reads_ && iter->Valid(); iter->Prev()) {-      bytes += iter->key().size() + iter->value().size();-      thread->stats.FinishedSingleOp();-      ++i;-    }-    delete iter;-    thread->stats.AddBytes(bytes);-  }--  void ReadRandom(ThreadState* thread) {-    ReadOptions options;-    std::string value;-    for (int i = 0; i < reads_; i++) {-      char key[100];-      const int k = thread->rand.Next() % FLAGS_num;-      snprintf(key, sizeof(key), "%016d", k);-      db_->Get(options, key, &value);-      thread->stats.FinishedSingleOp();-    }-  }--  void ReadHot(ThreadState* thread) {-    ReadOptions options;-    std::string value;-    const int range = (FLAGS_num + 99) / 100;-    for (int i = 0; i < reads_; i++) {-      char key[100];-      const int k = thread->rand.Next() % range;-      snprintf(key, sizeof(key), "%016d", k);-      db_->Get(options, key, &value);-      thread->stats.FinishedSingleOp();-    }-  }--  void ReadWhileWriting(ThreadState* thread) {-    if (thread->tid > 0) {-      ReadRandom(thread);-    } else {-      // Special thread that keeps writing until other threads are done.-      RandomGenerator gen;-      while (true) {-        {-          MutexLock l(&thread->shared->mu);-          if (thread->shared->num_done + 1 >= thread->shared->num_initialized) {-            // Other threads have finished-            break;-          }-        }--        const int k = thread->rand.Next() % FLAGS_num;-        char key[100];-        snprintf(key, sizeof(key), "%016d", k);-        Status s = db_->Put(write_options_, key, gen.Generate(value_size_));-        if (!s.ok()) {-          fprintf(stderr, "put error: %s\n", s.ToString().c_str());-          exit(1);-        }-      }--      // Do not count any of the preceding work/delay in stats.-      thread->stats.Start();-    }-  }--  void Compact(ThreadState* thread) {-    db_->CompactRange(NULL, NULL);-  }--  void PrintStats() {-    std::string stats;-    if (!db_->GetProperty("leveldb.stats", &stats)) {-      stats = "(failed)";-    }-    fprintf(stdout, "\n%s\n", stats.c_str());-  }--  static void WriteToFile(void* arg, const char* buf, int n) {-    reinterpret_cast<WritableFile*>(arg)->Append(Slice(buf, n));-  }--  void HeapProfile() {-    char fname[100];-    snprintf(fname, sizeof(fname), "%s/heap-%04d", FLAGS_db, ++heap_counter_);-    WritableFile* file;-    Status s = Env::Default()->NewWritableFile(fname, &file);-    if (!s.ok()) {-      fprintf(stderr, "%s\n", s.ToString().c_str());-      return;-    }-    bool ok = port::GetHeapProfile(WriteToFile, file);-    delete file;-    if (!ok) {-      fprintf(stderr, "heap profiling not supported\n");-      Env::Default()->DeleteFile(fname);-    }-  }-};--}  // namespace leveldb--int main(int argc, char** argv) {-  FLAGS_write_buffer_size = leveldb::Options().write_buffer_size;-  FLAGS_open_files = leveldb::Options().max_open_files;--  for (int i = 1; i < argc; i++) {-    double d;-    int n;-    char junk;-    if (leveldb::Slice(argv[i]).starts_with("--benchmarks=")) {-      FLAGS_benchmarks = argv[i] + strlen("--benchmarks=");-    } else if (sscanf(argv[i], "--compression_ratio=%lf%c", &d, &junk) == 1) {-      FLAGS_compression_ratio = d;-    } else if (sscanf(argv[i], "--histogram=%d%c", &n, &junk) == 1 &&-               (n == 0 || n == 1)) {-      FLAGS_histogram = n;-    } else if (sscanf(argv[i], "--use_existing_db=%d%c", &n, &junk) == 1 &&-               (n == 0 || n == 1)) {-      FLAGS_use_existing_db = n;-    } else if (sscanf(argv[i], "--num=%d%c", &n, &junk) == 1) {-      FLAGS_num = n;-    } else if (sscanf(argv[i], "--reads=%d%c", &n, &junk) == 1) {-      FLAGS_reads = n;-    } else if (sscanf(argv[i], "--threads=%d%c", &n, &junk) == 1) {-      FLAGS_threads = n;-    } else if (sscanf(argv[i], "--value_size=%d%c", &n, &junk) == 1) {-      FLAGS_value_size = n;-    } else if (sscanf(argv[i], "--write_buffer_size=%d%c", &n, &junk) == 1) {-      FLAGS_write_buffer_size = n;-    } else if (sscanf(argv[i], "--cache_size=%d%c", &n, &junk) == 1) {-      FLAGS_cache_size = n;-    } else if (sscanf(argv[i], "--open_files=%d%c", &n, &junk) == 1) {-      FLAGS_open_files = n;-    } else if (strncmp(argv[i], "--db=", 5) == 0) {-      FLAGS_db = argv[i] + 5;-    } else {-      fprintf(stderr, "Invalid flag '%s'\n", argv[i]);-      exit(1);-    }-  }--  leveldb::Benchmark benchmark;-  benchmark.Run();-  return 0;-}

@@ -1,1444 +0,0 @@-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.-// Use of this source code is governed by a BSD-style license that can be-// found in the LICENSE file. See the AUTHORS file for names of contributors.--#include "db/db_impl.h"--#include <algorithm>-#include <set>-#include <string>-#include <stdint.h>-#include <stdio.h>-#include <vector>-#include "db/builder.h"-#include "db/db_iter.h"-#include "db/dbformat.h"-#include "db/filename.h"-#include "db/log_reader.h"-#include "db/log_writer.h"-#include "db/memtable.h"-#include "db/table_cache.h"-#include "db/version_set.h"-#include "db/write_batch_internal.h"-#include "leveldb/db.h"-#include "leveldb/env.h"-#include "leveldb/status.h"-#include "leveldb/table.h"-#include "leveldb/table_builder.h"-#include "port/port.h"-#include "table/block.h"-#include "table/merger.h"-#include "table/two_level_iterator.h"-#include "util/coding.h"-#include "util/logging.h"-#include "util/mutexlock.h"--namespace leveldb {--// Information kept for every waiting writer-struct DBImpl::Writer {-  Status status;-  WriteBatch* batch;-  bool sync;-  bool done;-  port::CondVar cv;--  explicit Writer(port::Mutex* mu) : cv(mu) { }-};--struct DBImpl::CompactionState {-  Compaction* const compaction;--  // Sequence numbers < smallest_snapshot are not significant since we-  // will never have to service a snapshot below smallest_snapshot.-  // Therefore if we have seen a sequence number S <= smallest_snapshot,-  // we can drop all entries for the same key with sequence numbers < S.-  SequenceNumber smallest_snapshot;--  // Files produced by compaction-  struct Output {-    uint64_t number;-    uint64_t file_size;-    InternalKey smallest, largest;-  };-  std::vector<Output> outputs;--  // State kept for output being generated-  WritableFile* outfile;-  TableBuilder* builder;--  uint64_t total_bytes;--  Output* current_output() { return &outputs[outputs.size()-1]; }--  explicit CompactionState(Compaction* c)-      : compaction(c),-        outfile(NULL),-        builder(NULL),-        total_bytes(0) {-  }-};--// Fix user-supplied options to be reasonable-template <class T,class V>-static void ClipToRange(T* ptr, V minvalue, V maxvalue) {-  if (static_cast<V>(*ptr) > maxvalue) *ptr = maxvalue;-  if (static_cast<V>(*ptr) < minvalue) *ptr = minvalue;-}-Options SanitizeOptions(const std::string& dbname,-                        const InternalKeyComparator* icmp,-                        const Options& src) {-  Options result = src;-  result.comparator = icmp;-  ClipToRange(&result.max_open_files,           20,     50000);-  ClipToRange(&result.write_buffer_size,        64<<10, 1<<30);-  ClipToRange(&result.block_size,               1<<10,  4<<20);-  if (result.info_log == NULL) {-    // Open a log file in the same directory as the db-    src.env->CreateDir(dbname);  // In case it does not exist-    src.env->RenameFile(InfoLogFileName(dbname), OldInfoLogFileName(dbname));-    Status s = src.env->NewLogger(InfoLogFileName(dbname), &result.info_log);-    if (!s.ok()) {-      // No place suitable for logging-      result.info_log = NULL;-    }-  }-  if (result.block_cache == NULL) {-    result.block_cache = NewLRUCache(8 << 20);-  }-  return result;-}--DBImpl::DBImpl(const Options& options, const std::string& dbname)-    : env_(options.env),-      internal_comparator_(options.comparator),-      options_(SanitizeOptions(dbname, &internal_comparator_, options)),-      owns_info_log_(options_.info_log != options.info_log),-      owns_cache_(options_.block_cache != options.block_cache),-      dbname_(dbname),-      db_lock_(NULL),-      shutting_down_(NULL),-      bg_cv_(&mutex_),-      mem_(new MemTable(internal_comparator_)),-      imm_(NULL),-      logfile_(NULL),-      logfile_number_(0),-      log_(NULL),-      tmp_batch_(new WriteBatch),-      bg_compaction_scheduled_(false),-      manual_compaction_(NULL) {-  mem_->Ref();-  has_imm_.Release_Store(NULL);--  // Reserve ten files or so for other uses and give the rest to TableCache.-  const int table_cache_size = options.max_open_files - 10;-  table_cache_ = new TableCache(dbname_, &options_, table_cache_size);--  versions_ = new VersionSet(dbname_, &options_, table_cache_,-                             &internal_comparator_);-}--DBImpl::~DBImpl() {-  // Wait for background work to finish-  mutex_.Lock();-  shutting_down_.Release_Store(this);  // Any non-NULL value is ok-  while (bg_compaction_scheduled_) {-    bg_cv_.Wait();-  }-  mutex_.Unlock();--  if (db_lock_ != NULL) {-    env_->UnlockFile(db_lock_);-  }--  delete versions_;-  if (mem_ != NULL) mem_->Unref();-  if (imm_ != NULL) imm_->Unref();-  delete tmp_batch_;-  delete log_;-  delete logfile_;-  delete table_cache_;--  if (owns_info_log_) {-    delete options_.info_log;-  }-  if (owns_cache_) {-    delete options_.block_cache;-  }-}--Status DBImpl::NewDB() {-  VersionEdit new_db;-  new_db.SetComparatorName(user_comparator()->Name());-  new_db.SetLogNumber(0);-  new_db.SetNextFile(2);-  new_db.SetLastSequence(0);--  const std::string manifest = DescriptorFileName(dbname_, 1);-  WritableFile* file;-  Status s = env_->NewWritableFile(manifest, &file);-  if (!s.ok()) {-    return s;-  }-  {-    log::Writer log(file);-    std::string record;-    new_db.EncodeTo(&record);-    s = log.AddRecord(record);-    if (s.ok()) {-      s = file->Close();-    }-  }-  delete file;-  if (s.ok()) {-    // Make "CURRENT" file that points to the new manifest file.-    s = SetCurrentFile(env_, dbname_, 1);-  } else {-    env_->DeleteFile(manifest);-  }-  return s;-}--void DBImpl::MaybeIgnoreError(Status* s) const {-  if (s->ok() || options_.paranoid_checks) {-    // No change needed-  } else {-    Log(options_.info_log, "Ignoring error %s", s->ToString().c_str());-    *s = Status::OK();-  }-}--void DBImpl::DeleteObsoleteFiles() {-  // Make a set of all of the live files-  std::set<uint64_t> live = pending_outputs_;-  versions_->AddLiveFiles(&live);--  std::vector<std::string> filenames;-  env_->GetChildren(dbname_, &filenames); // Ignoring errors on purpose-  uint64_t number;-  FileType type;-  for (size_t i = 0; i < filenames.size(); i++) {-    if (ParseFileName(filenames[i], &number, &type)) {-      bool keep = true;-      switch (type) {-        case kLogFile:-          keep = ((number >= versions_->LogNumber()) ||-                  (number == versions_->PrevLogNumber()));-          break;-        case kDescriptorFile:-          // Keep my manifest file, and any newer incarnations'-          // (in case there is a race that allows other incarnations)-          keep = (number >= versions_->ManifestFileNumber());-          break;-        case kTableFile:-          keep = (live.find(number) != live.end());-          break;-        case kTempFile:-          // Any temp files that are currently being written to must-          // be recorded in pending_outputs_, which is inserted into "live"-          keep = (live.find(number) != live.end());-          break;-        case kCurrentFile:-        case kDBLockFile:-        case kInfoLogFile:-          keep = true;-          break;-      }--      if (!keep) {-        if (type == kTableFile) {-          table_cache_->Evict(number);-        }-        Log(options_.info_log, "Delete type=%d #%lld\n",-            int(type),-            static_cast<unsigned long long>(number));-        env_->DeleteFile(dbname_ + "/" + filenames[i]);-      }-    }-  }-}--Status DBImpl::Recover(VersionEdit* edit) {-  mutex_.AssertHeld();--  // Ignore error from CreateDir since the creation of the DB is-  // committed only when the descriptor is created, and this directory-  // may already exist from a previous failed creation attempt.-  env_->CreateDir(dbname_);-  assert(db_lock_ == NULL);-  Status s = env_->LockFile(LockFileName(dbname_), &db_lock_);-  if (!s.ok()) {-    return s;-  }--  if (!env_->FileExists(CurrentFileName(dbname_))) {-    if (options_.create_if_missing) {-      s = NewDB();-      if (!s.ok()) {-        return s;-      }-    } else {-      return Status::InvalidArgument(-          dbname_, "does not exist (create_if_missing is false)");-    }-  } else {-    if (options_.error_if_exists) {-      return Status::InvalidArgument(-          dbname_, "exists (error_if_exists is true)");-    }-  }--  s = versions_->Recover();-  if (s.ok()) {-    SequenceNumber max_sequence(0);--    // Recover from all newer log files than the ones named in the-    // descriptor (new log files may have been added by the previous-    // incarnation without registering them in the descriptor).-    //-    // Note that PrevLogNumber() is no longer used, but we pay-    // attention to it in case we are recovering a database-    // produced by an older version of leveldb.-    const uint64_t min_log = versions_->LogNumber();-    const uint64_t prev_log = versions_->PrevLogNumber();-    std::vector<std::string> filenames;-    s = env_->GetChildren(dbname_, &filenames);-    if (!s.ok()) {-      return s;-    }-    uint64_t number;-    FileType type;-    std::vector<uint64_t> logs;-    for (size_t i = 0; i < filenames.size(); i++) {-      if (ParseFileName(filenames[i], &number, &type)-          && type == kLogFile-          && ((number >= min_log) || (number == prev_log))) {-        logs.push_back(number);-      }-    }--    // Recover in the order in which the logs were generated-    std::sort(logs.begin(), logs.end());-    for (size_t i = 0; i < logs.size(); i++) {-      s = RecoverLogFile(logs[i], edit, &max_sequence);--      // The previous incarnation may not have written any MANIFEST-      // records after allocating this log number.  So we manually-      // update the file number allocation counter in VersionSet.-      versions_->MarkFileNumberUsed(logs[i]);-    }--    if (s.ok()) {-      if (versions_->LastSequence() < max_sequence) {-        versions_->SetLastSequence(max_sequence);-      }-    }-  }--  return s;-}--Status DBImpl::RecoverLogFile(uint64_t log_number,-                              VersionEdit* edit,-                              SequenceNumber* max_sequence) {-  struct LogReporter : public log::Reader::Reporter {-    Env* env;-    Logger* info_log;-    const char* fname;-    Status* status;  // NULL if options_.paranoid_checks==false-    virtual void Corruption(size_t bytes, const Status& s) {-      Log(info_log, "%s%s: dropping %d bytes; %s",-          (this->status == NULL ? "(ignoring error) " : ""),-          fname, static_cast<int>(bytes), s.ToString().c_str());-      if (this->status != NULL && this->status->ok()) *this->status = s;-    }-  };--  mutex_.AssertHeld();--  // Open the log file-  std::string fname = LogFileName(dbname_, log_number);-  SequentialFile* file;-  Status status = env_->NewSequentialFile(fname, &file);-  if (!status.ok()) {-    MaybeIgnoreError(&status);-    return status;-  }--  // Create the log reader.-  LogReporter reporter;-  reporter.env = env_;-  reporter.info_log = options_.info_log;-  reporter.fname = fname.c_str();-  reporter.status = (options_.paranoid_checks ? &status : NULL);-  // We intentially make log::Reader do checksumming even if-  // paranoid_checks==false so that corruptions cause entire commits-  // to be skipped instead of propagating bad information (like overly-  // large sequence numbers).-  log::Reader reader(file, &reporter, true/*checksum*/,-                     0/*initial_offset*/);-  Log(options_.info_log, "Recovering log #%llu",-      (unsigned long long) log_number);--  // Read all the records and add to a memtable-  std::string scratch;-  Slice record;-  WriteBatch batch;-  MemTable* mem = NULL;-  while (reader.ReadRecord(&record, &scratch) &&-         status.ok()) {-    if (record.size() < 12) {-      reporter.Corruption(-          record.size(), Status::Corruption("log record too small"));-      continue;-    }-    WriteBatchInternal::SetContents(&batch, record);--    if (mem == NULL) {-      mem = new MemTable(internal_comparator_);-      mem->Ref();-    }-    status = WriteBatchInternal::InsertInto(&batch, mem);-    MaybeIgnoreError(&status);-    if (!status.ok()) {-      break;-    }-    const SequenceNumber last_seq =-        WriteBatchInternal::Sequence(&batch) +-        WriteBatchInternal::Count(&batch) - 1;-    if (last_seq > *max_sequence) {-      *max_sequence = last_seq;-    }--    if (mem->ApproximateMemoryUsage() > options_.write_buffer_size) {-      status = WriteLevel0Table(mem, edit, NULL);-      if (!status.ok()) {-        // Reflect errors immediately so that conditions like full-        // file-systems cause the DB::Open() to fail.-        break;-      }-      mem->Unref();-      mem = NULL;-    }-  }--  if (status.ok() && mem != NULL) {-    status = WriteLevel0Table(mem, edit, NULL);-    // Reflect errors immediately so that conditions like full-    // file-systems cause the DB::Open() to fail.-  }--  if (mem != NULL) mem->Unref();-  delete file;-  return status;-}--Status DBImpl::WriteLevel0Table(MemTable* mem, VersionEdit* edit,-                                Version* base) {-  mutex_.AssertHeld();-  const uint64_t start_micros = env_->NowMicros();-  FileMetaData meta;-  meta.number = versions_->NewFileNumber();-  pending_outputs_.insert(meta.number);-  Iterator* iter = mem->NewIterator();-  Log(options_.info_log, "Level-0 table #%llu: started",-      (unsigned long long) meta.number);--  Status s;-  {-    mutex_.Unlock();-    s = BuildTable(dbname_, env_, options_, table_cache_, iter, &meta);-    mutex_.Lock();-  }--  Log(options_.info_log, "Level-0 table #%llu: %lld bytes %s",-      (unsigned long long) meta.number,-      (unsigned long long) meta.file_size,-      s.ToString().c_str());-  delete iter;-  pending_outputs_.erase(meta.number);---  // Note that if file_size is zero, the file has been deleted and-  // should not be added to the manifest.-  int level = 0;-  if (s.ok() && meta.file_size > 0) {-    const Slice min_user_key = meta.smallest.user_key();-    const Slice max_user_key = meta.largest.user_key();-    if (base != NULL) {-      level = base->PickLevelForMemTableOutput(min_user_key, max_user_key);-    }-    edit->AddFile(level, meta.number, meta.file_size,-                  meta.smallest, meta.largest);-  }--  CompactionStats stats;-  stats.micros = env_->NowMicros() - start_micros;-  stats.bytes_written = meta.file_size;-  stats_[level].Add(stats);-  return s;-}--Status DBImpl::CompactMemTable() {-  mutex_.AssertHeld();-  assert(imm_ != NULL);--  // Save the contents of the memtable as a new Table-  VersionEdit edit;-  Version* base = versions_->current();-  base->Ref();-  Status s = WriteLevel0Table(imm_, &edit, base);-  base->Unref();--  if (s.ok() && shutting_down_.Acquire_Load()) {-    s = Status::IOError("Deleting DB during memtable compaction");-  }--  // Replace immutable memtable with the generated Table-  if (s.ok()) {-    edit.SetPrevLogNumber(0);-    edit.SetLogNumber(logfile_number_);  // Earlier logs no longer needed-    s = versions_->LogAndApply(&edit, &mutex_);-  }--  if (s.ok()) {-    // Commit to the new state-    imm_->Unref();-    imm_ = NULL;-    has_imm_.Release_Store(NULL);-    DeleteObsoleteFiles();-  }--  return s;-}--void DBImpl::CompactRange(const Slice* begin, const Slice* end) {-  int max_level_with_files = 1;-  {-    MutexLock l(&mutex_);-    Version* base = versions_->current();-    for (int level = 1; level < config::kNumLevels; level++) {-      if (base->OverlapInLevel(level, begin, end)) {-        max_level_with_files = level;-      }-    }-  }-  TEST_CompactMemTable(); // TODO(sanjay): Skip if memtable does not overlap-  for (int level = 0; level < max_level_with_files; level++) {-    TEST_CompactRange(level, begin, end);-  }-}--void DBImpl::TEST_CompactRange(int level, const Slice* begin,const Slice* end) {-  assert(level >= 0);-  assert(level + 1 < config::kNumLevels);--  InternalKey begin_storage, end_storage;--  ManualCompaction manual;-  manual.level = level;-  manual.done = false;-  if (begin == NULL) {-    manual.begin = NULL;-  } else {-    begin_storage = InternalKey(*begin, kMaxSequenceNumber, kValueTypeForSeek);-    manual.begin = &begin_storage;-  }-  if (end == NULL) {-    manual.end = NULL;-  } else {-    end_storage = InternalKey(*end, 0, static_cast<ValueType>(0));-    manual.end = &end_storage;-  }--  MutexLock l(&mutex_);-  while (!manual.done) {-    while (manual_compaction_ != NULL) {-      bg_cv_.Wait();-    }-    manual_compaction_ = &manual;-    MaybeScheduleCompaction();-    while (manual_compaction_ == &manual) {-      bg_cv_.Wait();-    }-  }-}--Status DBImpl::TEST_CompactMemTable() {-  // NULL batch means just wait for earlier writes to be done-  Status s = Write(WriteOptions(), NULL);-  if (s.ok()) {-    // Wait until the compaction completes-    MutexLock l(&mutex_);-    while (imm_ != NULL && bg_error_.ok()) {-      bg_cv_.Wait();-    }-    if (imm_ != NULL) {-      s = bg_error_;-    }-  }-  return s;-}--void DBImpl::MaybeScheduleCompaction() {-  mutex_.AssertHeld();-  if (bg_compaction_scheduled_) {-    // Already scheduled-  } else if (shutting_down_.Acquire_Load()) {-    // DB is being deleted; no more background compactions-  } else if (imm_ == NULL &&-             manual_compaction_ == NULL &&-             !versions_->NeedsCompaction()) {-    // No work to be done-  } else {-    bg_compaction_scheduled_ = true;-    env_->Schedule(&DBImpl::BGWork, this);-  }-}--void DBImpl::BGWork(void* db) {-  reinterpret_cast<DBImpl*>(db)->BackgroundCall();-}--void DBImpl::BackgroundCall() {-  MutexLock l(&mutex_);-  assert(bg_compaction_scheduled_);-  if (!shutting_down_.Acquire_Load()) {-    BackgroundCompaction();-  }-  bg_compaction_scheduled_ = false;--  // Previous compaction may have produced too many files in a level,-  // so reschedule another compaction if needed.-  MaybeScheduleCompaction();-  bg_cv_.SignalAll();-}--void DBImpl::BackgroundCompaction() {-  mutex_.AssertHeld();--  if (imm_ != NULL) {-    CompactMemTable();-    return;-  }--  Compaction* c;-  bool is_manual = (manual_compaction_ != NULL);-  InternalKey manual_end;-  if (is_manual) {-    ManualCompaction* m = manual_compaction_;-    c = versions_->CompactRange(m->level, m->begin, m->end);-    m->done = (c == NULL);-    if (c != NULL) {-      manual_end = c->input(0, c->num_input_files(0) - 1)->largest;-    }-    Log(options_.info_log,-        "Manual compaction at level-%d from %s .. %s; will stop at %s\n",-        m->level,-        (m->begin ? m->begin->DebugString().c_str() : "(begin)"),-        (m->end ? m->end->DebugString().c_str() : "(end)"),-        (m->done ? "(end)" : manual_end.DebugString().c_str()));-  } else {-    c = versions_->PickCompaction();-  }--  Status status;-  if (c == NULL) {-    // Nothing to do-  } else if (!is_manual && c->IsTrivialMove()) {-    // Move file to next level-    assert(c->num_input_files(0) == 1);-    FileMetaData* f = c->input(0, 0);-    c->edit()->DeleteFile(c->level(), f->number);-    c->edit()->AddFile(c->level() + 1, f->number, f->file_size,-                       f->smallest, f->largest);-    status = versions_->LogAndApply(c->edit(), &mutex_);-    VersionSet::LevelSummaryStorage tmp;-    Log(options_.info_log, "Moved #%lld to level-%d %lld bytes %s: %s\n",-        static_cast<unsigned long long>(f->number),-        c->level() + 1,-        static_cast<unsigned long long>(f->file_size),-        status.ToString().c_str(),-        versions_->LevelSummary(&tmp));-  } else {-    CompactionState* compact = new CompactionState(c);-    status = DoCompactionWork(compact);-    CleanupCompaction(compact);-    c->ReleaseInputs();-    DeleteObsoleteFiles();-  }-  delete c;--  if (status.ok()) {-    // Done-  } else if (shutting_down_.Acquire_Load()) {-    // Ignore compaction errors found during shutting down-  } else {-    Log(options_.info_log,-        "Compaction error: %s", status.ToString().c_str());-    if (options_.paranoid_checks && bg_error_.ok()) {-      bg_error_ = status;-    }-  }--  if (is_manual) {-    ManualCompaction* m = manual_compaction_;-    if (!status.ok()) {-      m->done = true;-    }-    if (!m->done) {-      // We only compacted part of the requested range.  Update *m-      // to the range that is left to be compacted.-      m->tmp_storage = manual_end;-      m->begin = &m->tmp_storage;-    }-    manual_compaction_ = NULL;-  }-}--void DBImpl::CleanupCompaction(CompactionState* compact) {-  mutex_.AssertHeld();-  if (compact->builder != NULL) {-    // May happen if we get a shutdown call in the middle of compaction-    compact->builder->Abandon();-    delete compact->builder;-  } else {-    assert(compact->outfile == NULL);-  }-  delete compact->outfile;-  for (size_t i = 0; i < compact->outputs.size(); i++) {-    const CompactionState::Output& out = compact->outputs[i];-    pending_outputs_.erase(out.number);-  }-  delete compact;-}--Status DBImpl::OpenCompactionOutputFile(CompactionState* compact) {-  assert(compact != NULL);-  assert(compact->builder == NULL);-  uint64_t file_number;-  {-    mutex_.Lock();-    file_number = versions_->NewFileNumber();-    pending_outputs_.insert(file_number);-    CompactionState::Output out;-    out.number = file_number;-    out.smallest.Clear();-    out.largest.Clear();-    compact->outputs.push_back(out);-    mutex_.Unlock();-  }--  // Make the output file-  std::string fname = TableFileName(dbname_, file_number);-  Status s = env_->NewWritableFile(fname, &compact->outfile);-  if (s.ok()) {-    compact->builder = new TableBuilder(options_, compact->outfile);-  }-  return s;-}--Status DBImpl::FinishCompactionOutputFile(CompactionState* compact,-                                          Iterator* input) {-  assert(compact != NULL);-  assert(compact->outfile != NULL);-  assert(compact->builder != NULL);--  const uint64_t output_number = compact->current_output()->number;-  assert(output_number != 0);--  // Check for iterator errors-  Status s = input->status();-  const uint64_t current_entries = compact->builder->NumEntries();-  if (s.ok()) {-    s = compact->builder->Finish();-  } else {-    compact->builder->Abandon();-  }-  const uint64_t current_bytes = compact->builder->FileSize();-  compact->current_output()->file_size = current_bytes;-  compact->total_bytes += current_bytes;-  delete compact->builder;-  compact->builder = NULL;--  // Finish and check for file errors-  if (s.ok()) {-    s = compact->outfile->Sync();-  }-  if (s.ok()) {-    s = compact->outfile->Close();-  }-  delete compact->outfile;-  compact->outfile = NULL;--  if (s.ok() && current_entries > 0) {-    // Verify that the table is usable-    Iterator* iter = table_cache_->NewIterator(ReadOptions(),-                                               output_number,-                                               current_bytes);-    s = iter->status();-    delete iter;-    if (s.ok()) {-      Log(options_.info_log,-          "Generated table #%llu: %lld keys, %lld bytes",-          (unsigned long long) output_number,-          (unsigned long long) current_entries,-          (unsigned long long) current_bytes);-    }-  }-  return s;-}---Status DBImpl::InstallCompactionResults(CompactionState* compact) {-  mutex_.AssertHeld();-  Log(options_.info_log,  "Compacted %d@%d + %d@%d files => %lld bytes",-      compact->compaction->num_input_files(0),-      compact->compaction->level(),-      compact->compaction->num_input_files(1),-      compact->compaction->level() + 1,-      static_cast<long long>(compact->total_bytes));--  // Add compaction outputs-  compact->compaction->AddInputDeletions(compact->compaction->edit());-  const int level = compact->compaction->level();-  for (size_t i = 0; i < compact->outputs.size(); i++) {-    const CompactionState::Output& out = compact->outputs[i];-    compact->compaction->edit()->AddFile(-        level + 1,-        out.number, out.file_size, out.smallest, out.largest);-  }-  return versions_->LogAndApply(compact->compaction->edit(), &mutex_);-}--Status DBImpl::DoCompactionWork(CompactionState* compact) {-  const uint64_t start_micros = env_->NowMicros();-  int64_t imm_micros = 0;  // Micros spent doing imm_ compactions--  Log(options_.info_log,  "Compacting %d@%d + %d@%d files",-      compact->compaction->num_input_files(0),-      compact->compaction->level(),-      compact->compaction->num_input_files(1),-      compact->compaction->level() + 1);--  assert(versions_->NumLevelFiles(compact->compaction->level()) > 0);-  assert(compact->builder == NULL);-  assert(compact->outfile == NULL);-  if (snapshots_.empty()) {-    compact->smallest_snapshot = versions_->LastSequence();-  } else {-    compact->smallest_snapshot = snapshots_.oldest()->number_;-  }--  // Release mutex while we're actually doing the compaction work-  mutex_.Unlock();--  Iterator* input = versions_->MakeInputIterator(compact->compaction);-  input->SeekToFirst();-  Status status;-  ParsedInternalKey ikey;-  std::string current_user_key;-  bool has_current_user_key = false;-  SequenceNumber last_sequence_for_key = kMaxSequenceNumber;-  for (; input->Valid() && !shutting_down_.Acquire_Load(); ) {-    // Prioritize immutable compaction work-    if (has_imm_.NoBarrier_Load() != NULL) {-      const uint64_t imm_start = env_->NowMicros();-      mutex_.Lock();-      if (imm_ != NULL) {-        CompactMemTable();-        bg_cv_.SignalAll();  // Wakeup MakeRoomForWrite() if necessary-      }-      mutex_.Unlock();-      imm_micros += (env_->NowMicros() - imm_start);-    }--    Slice key = input->key();-    if (compact->compaction->ShouldStopBefore(key) &&-        compact->builder != NULL) {-      status = FinishCompactionOutputFile(compact, input);-      if (!status.ok()) {-        break;-      }-    }--    // Handle key/value, add to state, etc.-    bool drop = false;-    if (!ParseInternalKey(key, &ikey)) {-      // Do not hide error keys-      current_user_key.clear();-      has_current_user_key = false;-      last_sequence_for_key = kMaxSequenceNumber;-    } else {-      if (!has_current_user_key ||-          user_comparator()->Compare(ikey.user_key,-                                     Slice(current_user_key)) != 0) {-        // First occurrence of this user key-        current_user_key.assign(ikey.user_key.data(), ikey.user_key.size());-        has_current_user_key = true;-        last_sequence_for_key = kMaxSequenceNumber;-      }--      if (last_sequence_for_key <= compact->smallest_snapshot) {-        // Hidden by an newer entry for same user key-        drop = true;    // (A)-      } else if (ikey.type == kTypeDeletion &&-                 ikey.sequence <= compact->smallest_snapshot &&-                 compact->compaction->IsBaseLevelForKey(ikey.user_key)) {-        // For this user key:-        // (1) there is no data in higher levels-        // (2) data in lower levels will have larger sequence numbers-        // (3) data in layers that are being compacted here and have-        //     smaller sequence numbers will be dropped in the next-        //     few iterations of this loop (by rule (A) above).-        // Therefore this deletion marker is obsolete and can be dropped.-        drop = true;-      }--      last_sequence_for_key = ikey.sequence;-    }-#if 0-    Log(options_.info_log,-        "  Compact: %s, seq %d, type: %d %d, drop: %d, is_base: %d, "-        "%d smallest_snapshot: %d",-        ikey.user_key.ToString().c_str(),-        (int)ikey.sequence, ikey.type, kTypeValue, drop,-        compact->compaction->IsBaseLevelForKey(ikey.user_key),-        (int)last_sequence_for_key, (int)compact->smallest_snapshot);-#endif--    if (!drop) {-      // Open output file if necessary-      if (compact->builder == NULL) {-        status = OpenCompactionOutputFile(compact);-        if (!status.ok()) {-          break;-        }-      }-      if (compact->builder->NumEntries() == 0) {-        compact->current_output()->smallest.DecodeFrom(key);-      }-      compact->current_output()->largest.DecodeFrom(key);-      compact->builder->Add(key, input->value());--      // Close output file if it is big enough-      if (compact->builder->FileSize() >=-          compact->compaction->MaxOutputFileSize()) {-        status = FinishCompactionOutputFile(compact, input);-        if (!status.ok()) {-          break;-        }-      }-    }--    input->Next();-  }--  if (status.ok() && shutting_down_.Acquire_Load()) {-    status = Status::IOError("Deleting DB during compaction");-  }-  if (status.ok() && compact->builder != NULL) {-    status = FinishCompactionOutputFile(compact, input);-  }-  if (status.ok()) {-    status = input->status();-  }-  delete input;-  input = NULL;--  CompactionStats stats;-  stats.micros = env_->NowMicros() - start_micros - imm_micros;-  for (int which = 0; which < 2; which++) {-    for (int i = 0; i < compact->compaction->num_input_files(which); i++) {-      stats.bytes_read += compact->compaction->input(which, i)->file_size;-    }-  }-  for (size_t i = 0; i < compact->outputs.size(); i++) {-    stats.bytes_written += compact->outputs[i].file_size;-  }--  mutex_.Lock();-  stats_[compact->compaction->level() + 1].Add(stats);--  if (status.ok()) {-    status = InstallCompactionResults(compact);-  }-  VersionSet::LevelSummaryStorage tmp;-  Log(options_.info_log,-      "compacted to: %s", versions_->LevelSummary(&tmp));-  return status;-}--namespace {-struct IterState {-  port::Mutex* mu;-  Version* version;-  MemTable* mem;-  MemTable* imm;-};--static void CleanupIteratorState(void* arg1, void* arg2) {-  IterState* state = reinterpret_cast<IterState*>(arg1);-  state->mu->Lock();-  state->mem->Unref();-  if (state->imm != NULL) state->imm->Unref();-  state->version->Unref();-  state->mu->Unlock();-  delete state;-}-}  // namespace--Iterator* DBImpl::NewInternalIterator(const ReadOptions& options,-                                      SequenceNumber* latest_snapshot) {-  IterState* cleanup = new IterState;-  mutex_.Lock();-  *latest_snapshot = versions_->LastSequence();--  // Collect together all needed child iterators-  std::vector<Iterator*> list;-  list.push_back(mem_->NewIterator());-  mem_->Ref();-  if (imm_ != NULL) {-    list.push_back(imm_->NewIterator());-    imm_->Ref();-  }-  versions_->current()->AddIterators(options, &list);-  Iterator* internal_iter =-      NewMergingIterator(&internal_comparator_, &list[0], list.size());-  versions_->current()->Ref();--  cleanup->mu = &mutex_;-  cleanup->mem = mem_;-  cleanup->imm = imm_;-  cleanup->version = versions_->current();-  internal_iter->RegisterCleanup(CleanupIteratorState, cleanup, NULL);--  mutex_.Unlock();-  return internal_iter;-}--Iterator* DBImpl::TEST_NewInternalIterator() {-  SequenceNumber ignored;-  return NewInternalIterator(ReadOptions(), &ignored);-}--int64_t DBImpl::TEST_MaxNextLevelOverlappingBytes() {-  MutexLock l(&mutex_);-  return versions_->MaxNextLevelOverlappingBytes();-}--Status DBImpl::Get(const ReadOptions& options,-                   const Slice& key,-                   std::string* value) {-  Status s;-  MutexLock l(&mutex_);-  SequenceNumber snapshot;-  if (options.snapshot != NULL) {-    snapshot = reinterpret_cast<const SnapshotImpl*>(options.snapshot)->number_;-  } else {-    snapshot = versions_->LastSequence();-  }--  MemTable* mem = mem_;-  MemTable* imm = imm_;-  Version* current = versions_->current();-  mem->Ref();-  if (imm != NULL) imm->Ref();-  current->Ref();--  bool have_stat_update = false;-  Version::GetStats stats;--  // Unlock while reading from files and memtables-  {-    mutex_.Unlock();-    // First look in the memtable, then in the immutable memtable (if any).-    LookupKey lkey(key, snapshot);-    if (mem->Get(lkey, value, &s)) {-      // Done-    } else if (imm != NULL && imm->Get(lkey, value, &s)) {-      // Done-    } else {-      s = current->Get(options, lkey, value, &stats);-      have_stat_update = true;-    }-    mutex_.Lock();-  }--  if (have_stat_update && current->UpdateStats(stats)) {-    MaybeScheduleCompaction();-  }-  mem->Unref();-  if (imm != NULL) imm->Unref();-  current->Unref();-  return s;-}--Iterator* DBImpl::NewIterator(const ReadOptions& options) {-  SequenceNumber latest_snapshot;-  Iterator* internal_iter = NewInternalIterator(options, &latest_snapshot);-  return NewDBIterator(-      &dbname_, env_, user_comparator(), internal_iter,-      (options.snapshot != NULL-       ? reinterpret_cast<const SnapshotImpl*>(options.snapshot)->number_-       : latest_snapshot));-}--const Snapshot* DBImpl::GetSnapshot() {-  MutexLock l(&mutex_);-  return snapshots_.New(versions_->LastSequence());-}--void DBImpl::ReleaseSnapshot(const Snapshot* s) {-  MutexLock l(&mutex_);-  snapshots_.Delete(reinterpret_cast<const SnapshotImpl*>(s));-}--// Convenience methods-Status DBImpl::Put(const WriteOptions& o, const Slice& key, const Slice& val) {-  return DB::Put(o, key, val);-}--Status DBImpl::Delete(const WriteOptions& options, const Slice& key) {-  return DB::Delete(options, key);-}--Status DBImpl::Write(const WriteOptions& options, WriteBatch* my_batch) {-  Writer w(&mutex_);-  w.batch = my_batch;-  w.sync = options.sync;-  w.done = false;--  MutexLock l(&mutex_);-  writers_.push_back(&w);-  while (!w.done && &w != writers_.front()) {-    w.cv.Wait();-  }-  if (w.done) {-    return w.status;-  }--  // May temporarily unlock and wait.-  Status status = MakeRoomForWrite(my_batch == NULL);-  uint64_t last_sequence = versions_->LastSequence();-  Writer* last_writer = &w;-  if (status.ok() && my_batch != NULL) {  // NULL batch is for compactions-    WriteBatch* updates = BuildBatchGroup(&last_writer);-    WriteBatchInternal::SetSequence(updates, last_sequence + 1);-    last_sequence += WriteBatchInternal::Count(updates);--    // Add to log and apply to memtable.  We can release the lock-    // during this phase since &w is currently responsible for logging-    // and protects against concurrent loggers and concurrent writes-    // into mem_.-    {-      mutex_.Unlock();-      status = log_->AddRecord(WriteBatchInternal::Contents(updates));-      if (status.ok() && options.sync) {-        status = logfile_->Sync();-      }-      if (status.ok()) {-        status = WriteBatchInternal::InsertInto(updates, mem_);-      }-      mutex_.Lock();-    }-    if (updates == tmp_batch_) tmp_batch_->Clear();--    versions_->SetLastSequence(last_sequence);-  }--  while (true) {-    Writer* ready = writers_.front();-    writers_.pop_front();-    if (ready != &w) {-      ready->status = status;-      ready->done = true;-      ready->cv.Signal();-    }-    if (ready == last_writer) break;-  }--  // Notify new head of write queue-  if (!writers_.empty()) {-    writers_.front()->cv.Signal();-  }--  return status;-}--// REQUIRES: Writer list must be non-empty-// REQUIRES: First writer must have a non-NULL batch-WriteBatch* DBImpl::BuildBatchGroup(Writer** last_writer) {-  assert(!writers_.empty());-  Writer* first = writers_.front();-  WriteBatch* result = first->batch;-  assert(result != NULL);--  size_t size = WriteBatchInternal::ByteSize(first->batch);--  // Allow the group to grow up to a maximum size, but if the-  // original write is small, limit the growth so we do not slow-  // down the small write too much.-  size_t max_size = 1 << 20;-  if (size <= (128<<10)) {-    max_size = size + (128<<10);-  }--  *last_writer = first;-  std::deque<Writer*>::iterator iter = writers_.begin();-  ++iter;  // Advance past "first"-  for (; iter != writers_.end(); ++iter) {-    Writer* w = *iter;-    if (w->sync && !first->sync) {-      // Do not include a sync write into a batch handled by a non-sync write.-      break;-    }--    if (w->batch != NULL) {-      size += WriteBatchInternal::ByteSize(w->batch);-      if (size > max_size) {-        // Do not make batch too big-        break;-      }--      // Append to *reuslt-      if (result == first->batch) {-        // Switch to temporary batch instead of disturbing caller's batch-        result = tmp_batch_;-        assert(WriteBatchInternal::Count(result) == 0);-        WriteBatchInternal::Append(result, first->batch);-      }-      WriteBatchInternal::Append(result, w->batch);-    }-    *last_writer = w;-  }-  return result;-}--// REQUIRES: mutex_ is held-// REQUIRES: this thread is currently at the front of the writer queue-Status DBImpl::MakeRoomForWrite(bool force) {-  mutex_.AssertHeld();-  assert(!writers_.empty());-  bool allow_delay = !force;-  Status s;-  while (true) {-    if (!bg_error_.ok()) {-      // Yield previous error-      s = bg_error_;-      break;-    } else if (-        allow_delay &&-        versions_->NumLevelFiles(0) >= config::kL0_SlowdownWritesTrigger) {-      // We are getting close to hitting a hard limit on the number of-      // L0 files.  Rather than delaying a single write by several-      // seconds when we hit the hard limit, start delaying each-      // individual write by 1ms to reduce latency variance.  Also,-      // this delay hands over some CPU to the compaction thread in-      // case it is sharing the same core as the writer.-      mutex_.Unlock();-      env_->SleepForMicroseconds(1000);-      allow_delay = false;  // Do not delay a single write more than once-      mutex_.Lock();-    } else if (!force &&-               (mem_->ApproximateMemoryUsage() <= options_.write_buffer_size)) {-      // There is room in current memtable-      break;-    } else if (imm_ != NULL) {-      // We have filled up the current memtable, but the previous-      // one is still being compacted, so we wait.-      bg_cv_.Wait();-    } else if (versions_->NumLevelFiles(0) >= config::kL0_StopWritesTrigger) {-      // There are too many level-0 files.-      Log(options_.info_log, "waiting...\n");-      bg_cv_.Wait();-    } else {-      // Attempt to switch to a new memtable and trigger compaction of old-      assert(versions_->PrevLogNumber() == 0);-      uint64_t new_log_number = versions_->NewFileNumber();-      WritableFile* lfile = NULL;-      s = env_->NewWritableFile(LogFileName(dbname_, new_log_number), &lfile);-      if (!s.ok()) {-        break;-      }-      delete log_;-      delete logfile_;-      logfile_ = lfile;-      logfile_number_ = new_log_number;-      log_ = new log::Writer(lfile);-      imm_ = mem_;-      has_imm_.Release_Store(imm_);-      mem_ = new MemTable(internal_comparator_);-      mem_->Ref();-      force = false;   // Do not force another compaction if have room-      MaybeScheduleCompaction();-    }-  }-  return s;-}--bool DBImpl::GetProperty(const Slice& property, std::string* value) {-  value->clear();--  MutexLock l(&mutex_);-  Slice in = property;-  Slice prefix("leveldb.");-  if (!in.starts_with(prefix)) return false;-  in.remove_prefix(prefix.size());--  if (in.starts_with("num-files-at-level")) {-    in.remove_prefix(strlen("num-files-at-level"));-    uint64_t level;-    bool ok = ConsumeDecimalNumber(&in, &level) && in.empty();-    if (!ok || level >= config::kNumLevels) {-      return false;-    } else {-      char buf[100];-      snprintf(buf, sizeof(buf), "%d",-               versions_->NumLevelFiles(static_cast<int>(level)));-      *value = buf;-      return true;-    }-  } else if (in == "stats") {-    char buf[200];-    snprintf(buf, sizeof(buf),-             "                               Compactions\n"-             "Level  Files Size(MB) Time(sec) Read(MB) Write(MB)\n"-             "--------------------------------------------------\n"-             );-    value->append(buf);-    for (int level = 0; level < config::kNumLevels; level++) {-      int files = versions_->NumLevelFiles(level);-      if (stats_[level].micros > 0 || files > 0) {-        snprintf(-            buf, sizeof(buf),-            "%3d %8d %8.0f %9.0f %8.0f %9.0f\n",-            level,-            files,-            versions_->NumLevelBytes(level) / 1048576.0,-            stats_[level].micros / 1e6,-            stats_[level].bytes_read / 1048576.0,-            stats_[level].bytes_written / 1048576.0);-        value->append(buf);-      }-    }-    return true;-  } else if (in == "sstables") {-    *value = versions_->current()->DebugString();-    return true;-  }--  return false;-}--void DBImpl::GetApproximateSizes(-    const Range* range, int n,-    uint64_t* sizes) {-  // TODO(opt): better implementation-  Version* v;-  {-    MutexLock l(&mutex_);-    versions_->current()->Ref();-    v = versions_->current();-  }--  for (int i = 0; i < n; i++) {-    // Convert user_key into a corresponding internal key.-    InternalKey k1(range[i].start, kMaxSequenceNumber, kValueTypeForSeek);-    InternalKey k2(range[i].limit, kMaxSequenceNumber, kValueTypeForSeek);-    uint64_t start = versions_->ApproximateOffsetOf(v, k1);-    uint64_t limit = versions_->ApproximateOffsetOf(v, k2);-    sizes[i] = (limit >= start ? limit - start : 0);-  }--  {-    MutexLock l(&mutex_);-    v->Unref();-  }-}--// Default implementations of convenience methods that subclasses of DB-// can call if they wish-Status DB::Put(const WriteOptions& opt, const Slice& key, const Slice& value) {-  WriteBatch batch;-  batch.Put(key, value);-  return Write(opt, &batch);-}--Status DB::Delete(const WriteOptions& opt, const Slice& key) {-  WriteBatch batch;-  batch.Delete(key);-  return Write(opt, &batch);-}--DB::~DB() { }--Status DB::Open(const Options& options, const std::string& dbname,-                DB** dbptr) {-  *dbptr = NULL;--  DBImpl* impl = new DBImpl(options, dbname);-  impl->mutex_.Lock();-  VersionEdit edit;-  Status s = impl->Recover(&edit); // Handles create_if_missing, error_if_exists-  if (s.ok()) {-    uint64_t new_log_number = impl->versions_->NewFileNumber();-    WritableFile* lfile;-    s = options.env->NewWritableFile(LogFileName(dbname, new_log_number),-                                     &lfile);-    if (s.ok()) {-      edit.SetLogNumber(new_log_number);-      impl->logfile_ = lfile;-      impl->logfile_number_ = new_log_number;-      impl->log_ = new log::Writer(lfile);-      s = impl->versions_->LogAndApply(&edit, &impl->mutex_);-    }-    if (s.ok()) {-      impl->DeleteObsoleteFiles();-      impl->MaybeScheduleCompaction();-    }-  }-  impl->mutex_.Unlock();-  if (s.ok()) {-    *dbptr = impl;-  } else {-    delete impl;-  }-  return s;-}--Snapshot::~Snapshot() {-}--Status DestroyDB(const std::string& dbname, const Options& options) {-  Env* env = options.env;-  std::vector<std::string> filenames;-  // Ignore error in case directory does not exist-  env->GetChildren(dbname, &filenames);-  if (filenames.empty()) {-    return Status::OK();-  }--  FileLock* lock;-  const std::string lockname = LockFileName(dbname);-  Status result = env->LockFile(lockname, &lock);-  if (result.ok()) {-    uint64_t number;-    FileType type;-    for (size_t i = 0; i < filenames.size(); i++) {-      if (ParseFileName(filenames[i], &number, &type) &&-          type != kDBLockFile) {  // Lock file will be deleted at end-        Status del = env->DeleteFile(dbname + "/" + filenames[i]);-        if (result.ok() && !del.ok()) {-          result = del;-        }-      }-    }-    env->UnlockFile(lock);  // Ignore error since state is already gone-    env->DeleteFile(lockname);-    env->DeleteDir(dbname);  // Ignore error in case dir contains other files-  }-  return result;-}--}  // namespace leveldb

@@ -1,192 +0,0 @@-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.-// Use of this source code is governed by a BSD-style license that can be-// found in the LICENSE file. See the AUTHORS file for names of contributors.--#ifndef STORAGE_LEVELDB_DB_DB_IMPL_H_-#define STORAGE_LEVELDB_DB_DB_IMPL_H_--#include <deque>-#include <set>-#include "db/dbformat.h"-#include "db/log_writer.h"-#include "db/snapshot.h"-#include "leveldb/db.h"-#include "leveldb/env.h"-#include "port/port.h"--namespace leveldb {--class MemTable;-class TableCache;-class Version;-class VersionEdit;-class VersionSet;--class DBImpl : public DB {- public:-  DBImpl(const Options& options, const std::string& dbname);-  virtual ~DBImpl();--  // Implementations of the DB interface-  virtual Status Put(const WriteOptions&, const Slice& key, const Slice& value);-  virtual Status Delete(const WriteOptions&, const Slice& key);-  virtual Status Write(const WriteOptions& options, WriteBatch* updates);-  virtual Status Get(const ReadOptions& options,-                     const Slice& key,-                     std::string* value);-  virtual Iterator* NewIterator(const ReadOptions&);-  virtual const Snapshot* GetSnapshot();-  virtual void ReleaseSnapshot(const Snapshot* snapshot);-  virtual bool GetProperty(const Slice& property, std::string* value);-  virtual void GetApproximateSizes(const Range* range, int n, uint64_t* sizes);-  virtual void CompactRange(const Slice* begin, const Slice* end);--  // Extra methods (for testing) that are not in the public DB interface--  // Compact any files in the named level that overlap [*begin,*end]-  void TEST_CompactRange(int level, const Slice* begin, const Slice* end);--  // Force current memtable contents to be compacted.-  Status TEST_CompactMemTable();--  // Return an internal iterator over the current state of the database.-  // The keys of this iterator are internal keys (see format.h).-  // The returned iterator should be deleted when no longer needed.-  Iterator* TEST_NewInternalIterator();--  // Return the maximum overlapping data (in bytes) at next level for any-  // file at a level >= 1.-  int64_t TEST_MaxNextLevelOverlappingBytes();-- private:-  friend class DB;-  struct CompactionState;-  struct Writer;--  Iterator* NewInternalIterator(const ReadOptions&,-                                SequenceNumber* latest_snapshot);--  Status NewDB();--  // Recover the descriptor from persistent storage.  May do a significant-  // amount of work to recover recently logged updates.  Any changes to-  // be made to the descriptor are added to *edit.-  Status Recover(VersionEdit* edit);--  void MaybeIgnoreError(Status* s) const;--  // Delete any unneeded files and stale in-memory entries.-  void DeleteObsoleteFiles();--  // Compact the in-memory write buffer to disk.  Switches to a new-  // log-file/memtable and writes a new descriptor iff successful.-  Status CompactMemTable();--  Status RecoverLogFile(uint64_t log_number,-                        VersionEdit* edit,-                        SequenceNumber* max_sequence);--  Status WriteLevel0Table(MemTable* mem, VersionEdit* edit, Version* base);--  Status MakeRoomForWrite(bool force /* compact even if there is room? */);-  WriteBatch* BuildBatchGroup(Writer** last_writer);--  void MaybeScheduleCompaction();-  static void BGWork(void* db);-  void BackgroundCall();-  void BackgroundCompaction();-  void CleanupCompaction(CompactionState* compact);-  Status DoCompactionWork(CompactionState* compact);--  Status OpenCompactionOutputFile(CompactionState* compact);-  Status FinishCompactionOutputFile(CompactionState* compact, Iterator* input);-  Status InstallCompactionResults(CompactionState* compact);--  // Constant after construction-  Env* const env_;-  const InternalKeyComparator internal_comparator_;-  const Options options_;  // options_.comparator == &internal_comparator_-  bool owns_info_log_;-  bool owns_cache_;-  const std::string dbname_;--  // table_cache_ provides its own synchronization-  TableCache* table_cache_;--  // Lock over the persistent DB state.  Non-NULL iff successfully acquired.-  FileLock* db_lock_;--  // State below is protected by mutex_-  port::Mutex mutex_;-  port::AtomicPointer shutting_down_;-  port::CondVar bg_cv_;          // Signalled when background work finishes-  MemTable* mem_;-  MemTable* imm_;                // Memtable being compacted-  port::AtomicPointer has_imm_;  // So bg thread can detect non-NULL imm_-  WritableFile* logfile_;-  uint64_t logfile_number_;-  log::Writer* log_;--  // Queue of writers.-  std::deque<Writer*> writers_;-  WriteBatch* tmp_batch_;--  SnapshotList snapshots_;--  // Set of table files to protect from deletion because they are-  // part of ongoing compactions.-  std::set<uint64_t> pending_outputs_;--  // Has a background compaction been scheduled or is running?-  bool bg_compaction_scheduled_;--  // Information for a manual compaction-  struct ManualCompaction {-    int level;-    bool done;-    const InternalKey* begin;   // NULL means beginning of key range-    const InternalKey* end;     // NULL means end of key range-    InternalKey tmp_storage;    // Used to keep track of compaction progress-  };-  ManualCompaction* manual_compaction_;--  VersionSet* versions_;--  // Have we encountered a background error in paranoid mode?-  Status bg_error_;--  // Per level compaction stats.  stats_[level] stores the stats for-  // compactions that produced data for the specified "level".-  struct CompactionStats {-    int64_t micros;-    int64_t bytes_read;-    int64_t bytes_written;--    CompactionStats() : micros(0), bytes_read(0), bytes_written(0) { }--    void Add(const CompactionStats& c) {-      this->micros += c.micros;-      this->bytes_read += c.bytes_read;-      this->bytes_written += c.bytes_written;-    }-  };-  CompactionStats stats_[config::kNumLevels];--  // No copying allowed-  DBImpl(const DBImpl&);-  void operator=(const DBImpl&);--  const Comparator* user_comparator() const {-    return internal_comparator_.user_comparator();-  }-};--// Sanitize db options.  The caller should delete result.info_log if-// it is not equal to src.info_log.-extern Options SanitizeOptions(const std::string& db,-                               const InternalKeyComparator* icmp,-                               const Options& src);--}  // namespace leveldb--#endif  // STORAGE_LEVELDB_DB_DB_IMPL_H_

@@ -1,299 +0,0 @@-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.-// Use of this source code is governed by a BSD-style license that can be-// found in the LICENSE file. See the AUTHORS file for names of contributors.--#include "db/db_iter.h"--#include "db/filename.h"-#include "db/dbformat.h"-#include "leveldb/env.h"-#include "leveldb/iterator.h"-#include "port/port.h"-#include "util/logging.h"-#include "util/mutexlock.h"--namespace leveldb {--#if 0-static void DumpInternalIter(Iterator* iter) {-  for (iter->SeekToFirst(); iter->Valid(); iter->Next()) {-    ParsedInternalKey k;-    if (!ParseInternalKey(iter->key(), &k)) {-      fprintf(stderr, "Corrupt '%s'\n", EscapeString(iter->key()).c_str());-    } else {-      fprintf(stderr, "@ '%s'\n", k.DebugString().c_str());-    }-  }-}-#endif--namespace {--// Memtables and sstables that make the DB representation contain-// (userkey,seq,type) => uservalue entries.  DBIter-// combines multiple entries for the same userkey found in the DB-// representation into a single entry while accounting for sequence-// numbers, deletion markers, overwrites, etc.-class DBIter: public Iterator {- public:-  // Which direction is the iterator currently moving?-  // (1) When moving forward, the internal iterator is positioned at-  //     the exact entry that yields this->key(), this->value()-  // (2) When moving backwards, the internal iterator is positioned-  //     just before all entries whose user key == this->key().-  enum Direction {-    kForward,-    kReverse-  };--  DBIter(const std::string* dbname, Env* env,-         const Comparator* cmp, Iterator* iter, SequenceNumber s)-      : dbname_(dbname),-        env_(env),-        user_comparator_(cmp),-        iter_(iter),-        sequence_(s),-        direction_(kForward),-        valid_(false) {-  }-  virtual ~DBIter() {-    delete iter_;-  }-  virtual bool Valid() const { return valid_; }-  virtual Slice key() const {-    assert(valid_);-    return (direction_ == kForward) ? ExtractUserKey(iter_->key()) : saved_key_;-  }-  virtual Slice value() const {-    assert(valid_);-    return (direction_ == kForward) ? iter_->value() : saved_value_;-  }-  virtual Status status() const {-    if (status_.ok()) {-      return iter_->status();-    } else {-      return status_;-    }-  }--  virtual void Next();-  virtual void Prev();-  virtual void Seek(const Slice& target);-  virtual void SeekToFirst();-  virtual void SeekToLast();-- private:-  void FindNextUserEntry(bool skipping, std::string* skip);-  void FindPrevUserEntry();-  bool ParseKey(ParsedInternalKey* key);--  inline void SaveKey(const Slice& k, std::string* dst) {-    dst->assign(k.data(), k.size());-  }--  inline void ClearSavedValue() {-    if (saved_value_.capacity() > 1048576) {-      std::string empty;-      swap(empty, saved_value_);-    } else {-      saved_value_.clear();-    }-  }--  const std::string* const dbname_;-  Env* const env_;-  const Comparator* const user_comparator_;-  Iterator* const iter_;-  SequenceNumber const sequence_;--  Status status_;-  std::string saved_key_;     // == current key when direction_==kReverse-  std::string saved_value_;   // == current raw value when direction_==kReverse-  Direction direction_;-  bool valid_;--  // No copying allowed-  DBIter(const DBIter&);-  void operator=(const DBIter&);-};--inline bool DBIter::ParseKey(ParsedInternalKey* ikey) {-  if (!ParseInternalKey(iter_->key(), ikey)) {-    status_ = Status::Corruption("corrupted internal key in DBIter");-    return false;-  } else {-    return true;-  }-}--void DBIter::Next() {-  assert(valid_);--  if (direction_ == kReverse) {  // Switch directions?-    direction_ = kForward;-    // iter_ is pointing just before the entries for this->key(),-    // so advance into the range of entries for this->key() and then-    // use the normal skipping code below.-    if (!iter_->Valid()) {-      iter_->SeekToFirst();-    } else {-      iter_->Next();-    }-    if (!iter_->Valid()) {-      valid_ = false;-      saved_key_.clear();-      return;-    }-  }--  // Temporarily use saved_key_ as storage for key to skip.-  std::string* skip = &saved_key_;-  SaveKey(ExtractUserKey(iter_->key()), skip);-  FindNextUserEntry(true, skip);-}--void DBIter::FindNextUserEntry(bool skipping, std::string* skip) {-  // Loop until we hit an acceptable entry to yield-  assert(iter_->Valid());-  assert(direction_ == kForward);-  do {-    ParsedInternalKey ikey;-    if (ParseKey(&ikey) && ikey.sequence <= sequence_) {-      switch (ikey.type) {-        case kTypeDeletion:-          // Arrange to skip all upcoming entries for this key since-          // they are hidden by this deletion.-          SaveKey(ikey.user_key, skip);-          skipping = true;-          break;-        case kTypeValue:-          if (skipping &&-              user_comparator_->Compare(ikey.user_key, *skip) <= 0) {-            // Entry hidden-          } else {-            valid_ = true;-            saved_key_.clear();-            return;-          }-          break;-      }-    }-    iter_->Next();-  } while (iter_->Valid());-  saved_key_.clear();-  valid_ = false;-}--void DBIter::Prev() {-  assert(valid_);--  if (direction_ == kForward) {  // Switch directions?-    // iter_ is pointing at the current entry.  Scan backwards until-    // the key changes so we can use the normal reverse scanning code.-    assert(iter_->Valid());  // Otherwise valid_ would have been false-    SaveKey(ExtractUserKey(iter_->key()), &saved_key_);-    while (true) {-      iter_->Prev();-      if (!iter_->Valid()) {-        valid_ = false;-        saved_key_.clear();-        ClearSavedValue();-        return;-      }-      if (user_comparator_->Compare(ExtractUserKey(iter_->key()),-                                    saved_key_) < 0) {-        break;-      }-    }-    direction_ = kReverse;-  }--  FindPrevUserEntry();-}--void DBIter::FindPrevUserEntry() {-  assert(direction_ == kReverse);--  ValueType value_type = kTypeDeletion;-  if (iter_->Valid()) {-    do {-      ParsedInternalKey ikey;-      if (ParseKey(&ikey) && ikey.sequence <= sequence_) {-        if ((value_type != kTypeDeletion) &&-            user_comparator_->Compare(ikey.user_key, saved_key_) < 0) {-          // We encountered a non-deleted value in entries for previous keys,-          break;-        }-        value_type = ikey.type;-        if (value_type == kTypeDeletion) {-          saved_key_.clear();-          ClearSavedValue();-        } else {-          Slice raw_value = iter_->value();-          if (saved_value_.capacity() > raw_value.size() + 1048576) {-            std::string empty;-            swap(empty, saved_value_);-          }-          SaveKey(ExtractUserKey(iter_->key()), &saved_key_);-          saved_value_.assign(raw_value.data(), raw_value.size());-        }-      }-      iter_->Prev();-    } while (iter_->Valid());-  }--  if (value_type == kTypeDeletion) {-    // End-    valid_ = false;-    saved_key_.clear();-    ClearSavedValue();-    direction_ = kForward;-  } else {-    valid_ = true;-  }-}--void DBIter::Seek(const Slice& target) {-  direction_ = kForward;-  ClearSavedValue();-  saved_key_.clear();-  AppendInternalKey(-      &saved_key_, ParsedInternalKey(target, sequence_, kValueTypeForSeek));-  iter_->Seek(saved_key_);-  if (iter_->Valid()) {-    FindNextUserEntry(false, &saved_key_ /* temporary storage */);-  } else {-    valid_ = false;-  }-}--void DBIter::SeekToFirst() {-  direction_ = kForward;-  ClearSavedValue();-  iter_->SeekToFirst();-  if (iter_->Valid()) {-    FindNextUserEntry(false, &saved_key_ /* temporary storage */);-  } else {-    valid_ = false;-  }-}--void DBIter::SeekToLast() {-  direction_ = kReverse;-  ClearSavedValue();-  iter_->SeekToLast();-  FindPrevUserEntry();-}--}  // anonymous namespace--Iterator* NewDBIterator(-    const std::string* dbname,-    Env* env,-    const Comparator* user_key_comparator,-    Iterator* internal_iter,-    const SequenceNumber& sequence) {-  return new DBIter(dbname, env, user_key_comparator, internal_iter, sequence);-}--}  // namespace leveldb

@@ -1,26 +0,0 @@-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.-// Use of this source code is governed by a BSD-style license that can be-// found in the LICENSE file. See the AUTHORS file for names of contributors.--#ifndef STORAGE_LEVELDB_DB_DB_ITER_H_-#define STORAGE_LEVELDB_DB_DB_ITER_H_--#include <stdint.h>-#include "leveldb/db.h"-#include "db/dbformat.h"--namespace leveldb {--// Return a new iterator that converts internal keys (yielded by-// "*internal_iter") that were live at the specified "sequence" number-// into appropriate user keys.-extern Iterator* NewDBIterator(-    const std::string* dbname,-    Env* env,-    const Comparator* user_key_comparator,-    Iterator* internal_iter,-    const SequenceNumber& sequence);--}  // namespace leveldb--#endif  // STORAGE_LEVELDB_DB_DB_ITER_H_

@@ -1,1711 +0,0 @@-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.-// Use of this source code is governed by a BSD-style license that can be-// found in the LICENSE file. See the AUTHORS file for names of contributors.--#include "leveldb/db.h"-#include "db/db_impl.h"-#include "db/filename.h"-#include "db/version_set.h"-#include "db/write_batch_internal.h"-#include "leveldb/env.h"-#include "leveldb/table.h"-#include "util/logging.h"-#include "util/mutexlock.h"-#include "util/testharness.h"-#include "util/testutil.h"--namespace leveldb {--static std::string RandomString(Random* rnd, int len) {-  std::string r;-  test::RandomString(rnd, len, &r);-  return r;-}--// Special Env used to delay background operations-class SpecialEnv : public EnvWrapper {- public:-  // sstable Sync() calls are blocked while this pointer is non-NULL.-  port::AtomicPointer delay_sstable_sync_;--  // Simulate no-space errors while this pointer is non-NULL.-  port::AtomicPointer no_space_;--  explicit SpecialEnv(Env* base) : EnvWrapper(base) {-    delay_sstable_sync_.Release_Store(NULL);-    no_space_.Release_Store(NULL);-  }--  Status NewWritableFile(const std::string& f, WritableFile** r) {-    class SSTableFile : public WritableFile {-     private:-      SpecialEnv* env_;-      WritableFile* base_;--     public:-      SSTableFile(SpecialEnv* env, WritableFile* base)-          : env_(env),-            base_(base) {-      }-      ~SSTableFile() { delete base_; }-      Status Append(const Slice& data) {-        if (env_->no_space_.Acquire_Load() != NULL) {-          // Drop writes on the floor-          return Status::OK();-        } else {-          return base_->Append(data);-        }-      }-      Status Close() { return base_->Close(); }-      Status Flush() { return base_->Flush(); }-      Status Sync() {-        while (env_->delay_sstable_sync_.Acquire_Load() != NULL) {-          env_->SleepForMicroseconds(100000);-        }-        return base_->Sync();-      }-    };--    Status s = target()->NewWritableFile(f, r);-    if (s.ok()) {-      if (strstr(f.c_str(), ".sst") != NULL) {-        *r = new SSTableFile(this, *r);-      }-    }-    return s;-  }-};--class DBTest {- public:-  std::string dbname_;-  SpecialEnv* env_;-  DB* db_;--  Options last_options_;--  DBTest() : env_(new SpecialEnv(Env::Default())) {-    dbname_ = test::TmpDir() + "/db_test";-    DestroyDB(dbname_, Options());-    db_ = NULL;-    Reopen();-  }--  ~DBTest() {-    delete db_;-    DestroyDB(dbname_, Options());-    delete env_;-  }--  DBImpl* dbfull() {-    return reinterpret_cast<DBImpl*>(db_);-  }--  void Reopen(Options* options = NULL) {-    ASSERT_OK(TryReopen(options));-  }--  void DestroyAndReopen(Options* options = NULL) {-    delete db_;-    db_ = NULL;-    DestroyDB(dbname_, Options());-    ASSERT_OK(TryReopen(options));-  }--  Status TryReopen(Options* options) {-    delete db_;-    db_ = NULL;-    Options opts;-    if (options != NULL) {-      opts = *options;-    } else {-      opts.create_if_missing = true;-    }-    last_options_ = opts;--    return DB::Open(opts, dbname_, &db_);-  }--  Status Put(const std::string& k, const std::string& v) {-    return db_->Put(WriteOptions(), k, v);-  }--  Status Delete(const std::string& k) {-    return db_->Delete(WriteOptions(), k);-  }--  std::string Get(const std::string& k, const Snapshot* snapshot = NULL) {-    ReadOptions options;-    options.snapshot = snapshot;-    std::string result;-    Status s = db_->Get(options, k, &result);-    if (s.IsNotFound()) {-      result = "NOT_FOUND";-    } else if (!s.ok()) {-      result = s.ToString();-    }-    return result;-  }--  // Return a string that contains all key,value pairs in order,-  // formatted like "(k1->v1)(k2->v2)".-  std::string Contents() {-    std::vector<std::string> forward;-    std::string result;-    Iterator* iter = db_->NewIterator(ReadOptions());-    for (iter->SeekToFirst(); iter->Valid(); iter->Next()) {-      std::string s = IterStatus(iter);-      result.push_back('(');-      result.append(s);-      result.push_back(')');-      forward.push_back(s);-    }--    // Check reverse iteration results are the reverse of forward results-    int matched = 0;-    for (iter->SeekToLast(); iter->Valid(); iter->Prev()) {-      ASSERT_LT(matched, forward.size());-      ASSERT_EQ(IterStatus(iter), forward[forward.size() - matched - 1]);-      matched++;-    }-    ASSERT_EQ(matched, forward.size());--    delete iter;-    return result;-  }--  std::string AllEntriesFor(const Slice& user_key) {-    Iterator* iter = dbfull()->TEST_NewInternalIterator();-    InternalKey target(user_key, kMaxSequenceNumber, kTypeValue);-    iter->Seek(target.Encode());-    std::string result;-    if (!iter->status().ok()) {-      result = iter->status().ToString();-    } else {-      result = "[ ";-      bool first = true;-      while (iter->Valid()) {-        ParsedInternalKey ikey;-        if (!ParseInternalKey(iter->key(), &ikey)) {-          result += "CORRUPTED";-        } else {-          if (last_options_.comparator->Compare(-                  ikey.user_key, user_key) != 0) {-            break;-          }-          if (!first) {-            result += ", ";-          }-          first = false;-          switch (ikey.type) {-            case kTypeValue:-              result += iter->value().ToString();-              break;-            case kTypeDeletion:-              result += "DEL";-              break;-          }-        }-        iter->Next();-      }-      if (!first) {-        result += " ";-      }-      result += "]";-    }-    delete iter;-    return result;-  }--  int NumTableFilesAtLevel(int level) {-    std::string property;-    ASSERT_TRUE(-        db_->GetProperty("leveldb.num-files-at-level" + NumberToString(level),-                         &property));-    return atoi(property.c_str());-  }--  int TotalTableFiles() {-    int result = 0;-    for (int level = 0; level < config::kNumLevels; level++) {-      result += NumTableFilesAtLevel(level);-    }-    return result;-  }--  // Return spread of files per level-  std::string FilesPerLevel() {-    std::string result;-    int last_non_zero_offset = 0;-    for (int level = 0; level < config::kNumLevels; level++) {-      int f = NumTableFilesAtLevel(level);-      char buf[100];-      snprintf(buf, sizeof(buf), "%s%d", (level ? "," : ""), f);-      result += buf;-      if (f > 0) {-        last_non_zero_offset = result.size();-      }-    }-    result.resize(last_non_zero_offset);-    return result;-  }--  int CountFiles() {-    std::vector<std::string> files;-    env_->GetChildren(dbname_, &files);-    return static_cast<int>(files.size());-  }--  uint64_t Size(const Slice& start, const Slice& limit) {-    Range r(start, limit);-    uint64_t size;-    db_->GetApproximateSizes(&r, 1, &size);-    return size;-  }--  void Compact(const Slice& start, const Slice& limit) {-    db_->CompactRange(&start, &limit);-  }--  // Do n memtable compactions, each of which produces an sstable-  // covering the range [small,large].-  void MakeTables(int n, const std::string& small, const std::string& large) {-    for (int i = 0; i < n; i++) {-      Put(small, "begin");-      Put(large, "end");-      dbfull()->TEST_CompactMemTable();-    }-  }--  // Prevent pushing of new sstables into deeper levels by adding-  // tables that cover a specified range to all levels.-  void FillLevels(const std::string& smallest, const std::string& largest) {-    MakeTables(config::kNumLevels, smallest, largest);-  }--  void DumpFileCounts(const char* label) {-    fprintf(stderr, "---\n%s:\n", label);-    fprintf(stderr, "maxoverlap: %lld\n",-            static_cast<long long>(-                dbfull()->TEST_MaxNextLevelOverlappingBytes()));-    for (int level = 0; level < config::kNumLevels; level++) {-      int num = NumTableFilesAtLevel(level);-      if (num > 0) {-        fprintf(stderr, "  level %3d : %d files\n", level, num);-      }-    }-  }--  std::string DumpSSTableList() {-    std::string property;-    db_->GetProperty("leveldb.sstables", &property);-    return property;-  }--  std::string IterStatus(Iterator* iter) {-    std::string result;-    if (iter->Valid()) {-      result = iter->key().ToString() + "->" + iter->value().ToString();-    } else {-      result = "(invalid)";-    }-    return result;-  }-};--TEST(DBTest, Empty) {-  ASSERT_TRUE(db_ != NULL);-  ASSERT_EQ("NOT_FOUND", Get("foo"));-}--TEST(DBTest, ReadWrite) {-  ASSERT_OK(Put("foo", "v1"));-  ASSERT_EQ("v1", Get("foo"));-  ASSERT_OK(Put("bar", "v2"));-  ASSERT_OK(Put("foo", "v3"));-  ASSERT_EQ("v3", Get("foo"));-  ASSERT_EQ("v2", Get("bar"));-}--TEST(DBTest, PutDeleteGet) {-  ASSERT_OK(db_->Put(WriteOptions(), "foo", "v1"));-  ASSERT_EQ("v1", Get("foo"));-  ASSERT_OK(db_->Put(WriteOptions(), "foo", "v2"));-  ASSERT_EQ("v2", Get("foo"));-  ASSERT_OK(db_->Delete(WriteOptions(), "foo"));-  ASSERT_EQ("NOT_FOUND", Get("foo"));-}--TEST(DBTest, GetFromImmutableLayer) {-  Options options;-  options.env = env_;-  options.write_buffer_size = 100000;  // Small write buffer-  Reopen(&options);--  ASSERT_OK(Put("foo", "v1"));-  ASSERT_EQ("v1", Get("foo"));--  env_->delay_sstable_sync_.Release_Store(env_);   // Block sync calls-  Put("k1", std::string(100000, 'x'));             // Fill memtable-  Put("k2", std::string(100000, 'y'));             // Trigger compaction-  ASSERT_EQ("v1", Get("foo"));-  env_->delay_sstable_sync_.Release_Store(NULL);   // Release sync calls-}--TEST(DBTest, GetFromVersions) {-  ASSERT_OK(Put("foo", "v1"));-  dbfull()->TEST_CompactMemTable();-  ASSERT_EQ("v1", Get("foo"));-}--TEST(DBTest, GetSnapshot) {-  // Try with both a short key and a long key-  for (int i = 0; i < 2; i++) {-    std::string key = (i == 0) ? std::string("foo") : std::string(200, 'x');-    ASSERT_OK(Put(key, "v1"));-    const Snapshot* s1 = db_->GetSnapshot();-    ASSERT_OK(Put(key, "v2"));-    ASSERT_EQ("v2", Get(key));-    ASSERT_EQ("v1", Get(key, s1));-    dbfull()->TEST_CompactMemTable();-    ASSERT_EQ("v2", Get(key));-    ASSERT_EQ("v1", Get(key, s1));-    db_->ReleaseSnapshot(s1);-  }-}--TEST(DBTest, GetLevel0Ordering) {-  // Check that we process level-0 files in correct order.  The code-  // below generates two level-0 files where the earlier one comes-  // before the later one in the level-0 file list since the earlier-  // one has a smaller "smallest" key.-  ASSERT_OK(Put("bar", "b"));-  ASSERT_OK(Put("foo", "v1"));-  dbfull()->TEST_CompactMemTable();-  ASSERT_OK(Put("foo", "v2"));-  dbfull()->TEST_CompactMemTable();-  ASSERT_EQ("v2", Get("foo"));-}--TEST(DBTest, GetOrderedByLevels) {-  ASSERT_OK(Put("foo", "v1"));-  Compact("a", "z");-  ASSERT_EQ("v1", Get("foo"));-  ASSERT_OK(Put("foo", "v2"));-  ASSERT_EQ("v2", Get("foo"));-  dbfull()->TEST_CompactMemTable();-  ASSERT_EQ("v2", Get("foo"));-}--TEST(DBTest, GetPicksCorrectFile) {-  // Arrange to have multiple files in a non-level-0 level.-  ASSERT_OK(Put("a", "va"));-  Compact("a", "b");-  ASSERT_OK(Put("x", "vx"));-  Compact("x", "y");-  ASSERT_OK(Put("f", "vf"));-  Compact("f", "g");-  ASSERT_EQ("va", Get("a"));-  ASSERT_EQ("vf", Get("f"));-  ASSERT_EQ("vx", Get("x"));-}--TEST(DBTest, GetEncountersEmptyLevel) {-  // Arrange for the following to happen:-  //   * sstable A in level 0-  //   * nothing in level 1-  //   * sstable B in level 2-  // Then do enough Get() calls to arrange for an automatic compaction-  // of sstable A.  A bug would cause the compaction to be marked as-  // occuring at level 1 (instead of the correct level 0).--  // Step 1: First place sstables in levels 0 and 2-  int compaction_count = 0;-  while (NumTableFilesAtLevel(0) == 0 ||-         NumTableFilesAtLevel(2) == 0) {-    ASSERT_LE(compaction_count, 100) << "could not fill levels 0 and 2";-    compaction_count++;-    Put("a", "begin");-    Put("z", "end");-    dbfull()->TEST_CompactMemTable();-  }--  // Step 2: clear level 1 if necessary.-  dbfull()->TEST_CompactRange(1, NULL, NULL);-  ASSERT_EQ(NumTableFilesAtLevel(0), 1);-  ASSERT_EQ(NumTableFilesAtLevel(1), 0);-  ASSERT_EQ(NumTableFilesAtLevel(2), 1);--  // Step 3: read until level 0 compaction disappears.-  int read_count = 0;-  while (NumTableFilesAtLevel(0) > 0) {-    ASSERT_LE(read_count, 10000) << "did not trigger level 0 compaction";-    read_count++;-    ASSERT_EQ("NOT_FOUND", Get("missing"));-  }-}--TEST(DBTest, IterEmpty) {-  Iterator* iter = db_->NewIterator(ReadOptions());--  iter->SeekToFirst();-  ASSERT_EQ(IterStatus(iter), "(invalid)");--  iter->SeekToLast();-  ASSERT_EQ(IterStatus(iter), "(invalid)");--  iter->Seek("foo");-  ASSERT_EQ(IterStatus(iter), "(invalid)");--  delete iter;-}--TEST(DBTest, IterSingle) {-  ASSERT_OK(Put("a", "va"));-  Iterator* iter = db_->NewIterator(ReadOptions());--  iter->SeekToFirst();-  ASSERT_EQ(IterStatus(iter), "a->va");-  iter->Next();-  ASSERT_EQ(IterStatus(iter), "(invalid)");-  iter->SeekToFirst();-  ASSERT_EQ(IterStatus(iter), "a->va");-  iter->Prev();-  ASSERT_EQ(IterStatus(iter), "(invalid)");--  iter->SeekToLast();-  ASSERT_EQ(IterStatus(iter), "a->va");-  iter->Next();-  ASSERT_EQ(IterStatus(iter), "(invalid)");-  iter->SeekToLast();-  ASSERT_EQ(IterStatus(iter), "a->va");-  iter->Prev();-  ASSERT_EQ(IterStatus(iter), "(invalid)");--  iter->Seek("");-  ASSERT_EQ(IterStatus(iter), "a->va");-  iter->Next();-  ASSERT_EQ(IterStatus(iter), "(invalid)");--  iter->Seek("a");-  ASSERT_EQ(IterStatus(iter), "a->va");-  iter->Next();-  ASSERT_EQ(IterStatus(iter), "(invalid)");--  iter->Seek("b");-  ASSERT_EQ(IterStatus(iter), "(invalid)");--  delete iter;-}--TEST(DBTest, IterMulti) {-  ASSERT_OK(Put("a", "va"));-  ASSERT_OK(Put("b", "vb"));-  ASSERT_OK(Put("c", "vc"));-  Iterator* iter = db_->NewIterator(ReadOptions());--  iter->SeekToFirst();-  ASSERT_EQ(IterStatus(iter), "a->va");-  iter->Next();-  ASSERT_EQ(IterStatus(iter), "b->vb");-  iter->Next();-  ASSERT_EQ(IterStatus(iter), "c->vc");-  iter->Next();-  ASSERT_EQ(IterStatus(iter), "(invalid)");-  iter->SeekToFirst();-  ASSERT_EQ(IterStatus(iter), "a->va");-  iter->Prev();-  ASSERT_EQ(IterStatus(iter), "(invalid)");--  iter->SeekToLast();-  ASSERT_EQ(IterStatus(iter), "c->vc");-  iter->Prev();-  ASSERT_EQ(IterStatus(iter), "b->vb");-  iter->Prev();-  ASSERT_EQ(IterStatus(iter), "a->va");-  iter->Prev();-  ASSERT_EQ(IterStatus(iter), "(invalid)");-  iter->SeekToLast();-  ASSERT_EQ(IterStatus(iter), "c->vc");-  iter->Next();-  ASSERT_EQ(IterStatus(iter), "(invalid)");--  iter->Seek("");-  ASSERT_EQ(IterStatus(iter), "a->va");-  iter->Seek("a");-  ASSERT_EQ(IterStatus(iter), "a->va");-  iter->Seek("ax");-  ASSERT_EQ(IterStatus(iter), "b->vb");-  iter->Seek("b");-  ASSERT_EQ(IterStatus(iter), "b->vb");-  iter->Seek("z");-  ASSERT_EQ(IterStatus(iter), "(invalid)");--  // Switch from reverse to forward-  iter->SeekToLast();-  iter->Prev();-  iter->Prev();-  iter->Next();-  ASSERT_EQ(IterStatus(iter), "b->vb");--  // Switch from forward to reverse-  iter->SeekToFirst();-  iter->Next();-  iter->Next();-  iter->Prev();-  ASSERT_EQ(IterStatus(iter), "b->vb");--  // Make sure iter stays at snapshot-  ASSERT_OK(Put("a",  "va2"));-  ASSERT_OK(Put("a2", "va3"));-  ASSERT_OK(Put("b",  "vb2"));-  ASSERT_OK(Put("c",  "vc2"));-  ASSERT_OK(Delete("b"));-  iter->SeekToFirst();-  ASSERT_EQ(IterStatus(iter), "a->va");-  iter->Next();-  ASSERT_EQ(IterStatus(iter), "b->vb");-  iter->Next();-  ASSERT_EQ(IterStatus(iter), "c->vc");-  iter->Next();-  ASSERT_EQ(IterStatus(iter), "(invalid)");-  iter->SeekToLast();-  ASSERT_EQ(IterStatus(iter), "c->vc");-  iter->Prev();-  ASSERT_EQ(IterStatus(iter), "b->vb");-  iter->Prev();-  ASSERT_EQ(IterStatus(iter), "a->va");-  iter->Prev();-  ASSERT_EQ(IterStatus(iter), "(invalid)");--  delete iter;-}--TEST(DBTest, IterSmallAndLargeMix) {-  ASSERT_OK(Put("a", "va"));-  ASSERT_OK(Put("b", std::string(100000, 'b')));-  ASSERT_OK(Put("c", "vc"));-  ASSERT_OK(Put("d", std::string(100000, 'd')));-  ASSERT_OK(Put("e", std::string(100000, 'e')));--  Iterator* iter = db_->NewIterator(ReadOptions());--  iter->SeekToFirst();-  ASSERT_EQ(IterStatus(iter), "a->va");-  iter->Next();-  ASSERT_EQ(IterStatus(iter), "b->" + std::string(100000, 'b'));-  iter->Next();-  ASSERT_EQ(IterStatus(iter), "c->vc");-  iter->Next();-  ASSERT_EQ(IterStatus(iter), "d->" + std::string(100000, 'd'));-  iter->Next();-  ASSERT_EQ(IterStatus(iter), "e->" + std::string(100000, 'e'));-  iter->Next();-  ASSERT_EQ(IterStatus(iter), "(invalid)");--  iter->SeekToLast();-  ASSERT_EQ(IterStatus(iter), "e->" + std::string(100000, 'e'));-  iter->Prev();-  ASSERT_EQ(IterStatus(iter), "d->" + std::string(100000, 'd'));-  iter->Prev();-  ASSERT_EQ(IterStatus(iter), "c->vc");-  iter->Prev();-  ASSERT_EQ(IterStatus(iter), "b->" + std::string(100000, 'b'));-  iter->Prev();-  ASSERT_EQ(IterStatus(iter), "a->va");-  iter->Prev();-  ASSERT_EQ(IterStatus(iter), "(invalid)");--  delete iter;-}--TEST(DBTest, IterMultiWithDelete) {-  ASSERT_OK(Put("a", "va"));-  ASSERT_OK(Put("b", "vb"));-  ASSERT_OK(Put("c", "vc"));-  ASSERT_OK(Delete("b"));-  ASSERT_EQ("NOT_FOUND", Get("b"));--  Iterator* iter = db_->NewIterator(ReadOptions());-  iter->Seek("c");-  ASSERT_EQ(IterStatus(iter), "c->vc");-  iter->Prev();-  ASSERT_EQ(IterStatus(iter), "a->va");-  delete iter;-}--TEST(DBTest, Recover) {-  ASSERT_OK(Put("foo", "v1"));-  ASSERT_OK(Put("baz", "v5"));--  Reopen();-  ASSERT_EQ("v1", Get("foo"));--  ASSERT_EQ("v1", Get("foo"));-  ASSERT_EQ("v5", Get("baz"));-  ASSERT_OK(Put("bar", "v2"));-  ASSERT_OK(Put("foo", "v3"));--  Reopen();-  ASSERT_EQ("v3", Get("foo"));-  ASSERT_OK(Put("foo", "v4"));-  ASSERT_EQ("v4", Get("foo"));-  ASSERT_EQ("v2", Get("bar"));-  ASSERT_EQ("v5", Get("baz"));-}--TEST(DBTest, RecoveryWithEmptyLog) {-  ASSERT_OK(Put("foo", "v1"));-  ASSERT_OK(Put("foo", "v2"));-  Reopen();-  Reopen();-  ASSERT_OK(Put("foo", "v3"));-  Reopen();-  ASSERT_EQ("v3", Get("foo"));-}--// Check that writes done during a memtable compaction are recovered-// if the database is shutdown during the memtable compaction.-TEST(DBTest, RecoverDuringMemtableCompaction) {-  Options options;-  options.env = env_;-  options.write_buffer_size = 1000000;-  Reopen(&options);--  // Trigger a long memtable compaction and reopen the database during it-  ASSERT_OK(Put("foo", "v1"));                         // Goes to 1st log file-  ASSERT_OK(Put("big1", std::string(10000000, 'x')));  // Fills memtable-  ASSERT_OK(Put("big2", std::string(1000, 'y')));      // Triggers compaction-  ASSERT_OK(Put("bar", "v2"));                         // Goes to new log file--  Reopen(&options);-  ASSERT_EQ("v1", Get("foo"));-  ASSERT_EQ("v2", Get("bar"));-  ASSERT_EQ(std::string(10000000, 'x'), Get("big1"));-  ASSERT_EQ(std::string(1000, 'y'), Get("big2"));-}--static std::string Key(int i) {-  char buf[100];-  snprintf(buf, sizeof(buf), "key%06d", i);-  return std::string(buf);-}--TEST(DBTest, MinorCompactionsHappen) {-  Options options;-  options.write_buffer_size = 10000;-  Reopen(&options);--  const int N = 500;--  int starting_num_tables = TotalTableFiles();-  for (int i = 0; i < N; i++) {-    ASSERT_OK(Put(Key(i), Key(i) + std::string(1000, 'v')));-  }-  int ending_num_tables = TotalTableFiles();-  ASSERT_GT(ending_num_tables, starting_num_tables);--  for (int i = 0; i < N; i++) {-    ASSERT_EQ(Key(i) + std::string(1000, 'v'), Get(Key(i)));-  }--  Reopen();--  for (int i = 0; i < N; i++) {-    ASSERT_EQ(Key(i) + std::string(1000, 'v'), Get(Key(i)));-  }-}--TEST(DBTest, RecoverWithLargeLog) {-  {-    Options options;-    Reopen(&options);-    ASSERT_OK(Put("big1", std::string(200000, '1')));-    ASSERT_OK(Put("big2", std::string(200000, '2')));-    ASSERT_OK(Put("small3", std::string(10, '3')));-    ASSERT_OK(Put("small4", std::string(10, '4')));-    ASSERT_EQ(NumTableFilesAtLevel(0), 0);-  }--  // Make sure that if we re-open with a small write buffer size that-  // we flush table files in the middle of a large log file.-  Options options;-  options.write_buffer_size = 100000;-  Reopen(&options);-  ASSERT_EQ(NumTableFilesAtLevel(0), 3);-  ASSERT_EQ(std::string(200000, '1'), Get("big1"));-  ASSERT_EQ(std::string(200000, '2'), Get("big2"));-  ASSERT_EQ(std::string(10, '3'), Get("small3"));-  ASSERT_EQ(std::string(10, '4'), Get("small4"));-  ASSERT_GT(NumTableFilesAtLevel(0), 1);-}--TEST(DBTest, CompactionsGenerateMultipleFiles) {-  Options options;-  options.write_buffer_size = 100000000;        // Large write buffer-  Reopen(&options);--  Random rnd(301);--  // Write 8MB (80 values, each 100K)-  ASSERT_EQ(NumTableFilesAtLevel(0), 0);-  std::vector<std::string> values;-  for (int i = 0; i < 80; i++) {-    values.push_back(RandomString(&rnd, 100000));-    ASSERT_OK(Put(Key(i), values[i]));-  }--  // Reopening moves updates to level-0-  Reopen(&options);-  dbfull()->TEST_CompactRange(0, NULL, NULL);--  ASSERT_EQ(NumTableFilesAtLevel(0), 0);-  ASSERT_GT(NumTableFilesAtLevel(1), 1);-  for (int i = 0; i < 80; i++) {-    ASSERT_EQ(Get(Key(i)), values[i]);-  }-}--TEST(DBTest, RepeatedWritesToSameKey) {-  Options options;-  options.env = env_;-  options.write_buffer_size = 100000;  // Small write buffer-  Reopen(&options);--  // We must have at most one file per level except for level-0,-  // which may have up to kL0_StopWritesTrigger files.-  const int kMaxFiles = config::kNumLevels + config::kL0_StopWritesTrigger;--  Random rnd(301);-  std::string value = RandomString(&rnd, 2 * options.write_buffer_size);-  for (int i = 0; i < 5 * kMaxFiles; i++) {-    Put("key", value);-    ASSERT_LE(TotalTableFiles(), kMaxFiles);-    fprintf(stderr, "after %d: %d files\n", int(i+1), TotalTableFiles());-  }-}--TEST(DBTest, SparseMerge) {-  Options options;-  options.compression = kNoCompression;-  Reopen(&options);--  FillLevels("A", "Z");--  // Suppose there is:-  //    small amount of data with prefix A-  //    large amount of data with prefix B-  //    small amount of data with prefix C-  // and that recent updates have made small changes to all three prefixes.-  // Check that we do not do a compaction that merges all of B in one shot.-  const std::string value(1000, 'x');-  Put("A", "va");-  // Write approximately 100MB of "B" values-  for (int i = 0; i < 100000; i++) {-    char key[100];-    snprintf(key, sizeof(key), "B%010d", i);-    Put(key, value);-  }-  Put("C", "vc");-  dbfull()->TEST_CompactMemTable();-  dbfull()->TEST_CompactRange(0, NULL, NULL);--  // Make sparse update-  Put("A",    "va2");-  Put("B100", "bvalue2");-  Put("C",    "vc2");-  dbfull()->TEST_CompactMemTable();--  // Compactions should not cause us to create a situation where-  // a file overlaps too much data at the next level.-  ASSERT_LE(dbfull()->TEST_MaxNextLevelOverlappingBytes(), 20*1048576);-  dbfull()->TEST_CompactRange(0, NULL, NULL);-  ASSERT_LE(dbfull()->TEST_MaxNextLevelOverlappingBytes(), 20*1048576);-  dbfull()->TEST_CompactRange(1, NULL, NULL);-  ASSERT_LE(dbfull()->TEST_MaxNextLevelOverlappingBytes(), 20*1048576);-}--static bool Between(uint64_t val, uint64_t low, uint64_t high) {-  bool result = (val >= low) && (val <= high);-  if (!result) {-    fprintf(stderr, "Value %llu is not in range [%llu, %llu]\n",-            (unsigned long long)(val),-            (unsigned long long)(low),-            (unsigned long long)(high));-  }-  return result;-}--TEST(DBTest, ApproximateSizes) {-  Options options;-  options.write_buffer_size = 100000000;        // Large write buffer-  options.compression = kNoCompression;-  DestroyAndReopen();--  ASSERT_TRUE(Between(Size("", "xyz"), 0, 0));-  Reopen(&options);-  ASSERT_TRUE(Between(Size("", "xyz"), 0, 0));--  // Write 8MB (80 values, each 100K)-  ASSERT_EQ(NumTableFilesAtLevel(0), 0);-  const int N = 80;-  Random rnd(301);-  for (int i = 0; i < N; i++) {-    ASSERT_OK(Put(Key(i), RandomString(&rnd, 100000)));-  }--  // 0 because GetApproximateSizes() does not account for memtable space-  ASSERT_TRUE(Between(Size("", Key(50)), 0, 0));--  // Check sizes across recovery by reopening a few times-  for (int run = 0; run < 3; run++) {-    Reopen(&options);--    for (int compact_start = 0; compact_start < N; compact_start += 10) {-      for (int i = 0; i < N; i += 10) {-        ASSERT_TRUE(Between(Size("", Key(i)), 100000*i, 100000*i + 10000));-        ASSERT_TRUE(Between(Size("", Key(i)+".suffix"),-                            100000 * (i+1), 100000 * (i+1) + 10000));-        ASSERT_TRUE(Between(Size(Key(i), Key(i+10)),-                            100000 * 10, 100000 * 10 + 10000));-      }-      ASSERT_TRUE(Between(Size("", Key(50)), 5000000, 5010000));-      ASSERT_TRUE(Between(Size("", Key(50)+".suffix"), 5100000, 5110000));--      std::string cstart_str = Key(compact_start);-      std::string cend_str = Key(compact_start + 9);-      Slice cstart = cstart_str;-      Slice cend = cend_str;-      dbfull()->TEST_CompactRange(0, &cstart, &cend);-    }--    ASSERT_EQ(NumTableFilesAtLevel(0), 0);-    ASSERT_GT(NumTableFilesAtLevel(1), 0);-  }-}--TEST(DBTest, ApproximateSizes_MixOfSmallAndLarge) {-  Options options;-  options.compression = kNoCompression;-  Reopen();--  Random rnd(301);-  std::string big1 = RandomString(&rnd, 100000);-  ASSERT_OK(Put(Key(0), RandomString(&rnd, 10000)));-  ASSERT_OK(Put(Key(1), RandomString(&rnd, 10000)));-  ASSERT_OK(Put(Key(2), big1));-  ASSERT_OK(Put(Key(3), RandomString(&rnd, 10000)));-  ASSERT_OK(Put(Key(4), big1));-  ASSERT_OK(Put(Key(5), RandomString(&rnd, 10000)));-  ASSERT_OK(Put(Key(6), RandomString(&rnd, 300000)));-  ASSERT_OK(Put(Key(7), RandomString(&rnd, 10000)));--  // Check sizes across recovery by reopening a few times-  for (int run = 0; run < 3; run++) {-    Reopen(&options);--    ASSERT_TRUE(Between(Size("", Key(0)), 0, 0));-    ASSERT_TRUE(Between(Size("", Key(1)), 10000, 11000));-    ASSERT_TRUE(Between(Size("", Key(2)), 20000, 21000));-    ASSERT_TRUE(Between(Size("", Key(3)), 120000, 121000));-    ASSERT_TRUE(Between(Size("", Key(4)), 130000, 131000));-    ASSERT_TRUE(Between(Size("", Key(5)), 230000, 231000));-    ASSERT_TRUE(Between(Size("", Key(6)), 240000, 241000));-    ASSERT_TRUE(Between(Size("", Key(7)), 540000, 541000));-    ASSERT_TRUE(Between(Size("", Key(8)), 550000, 551000));--    ASSERT_TRUE(Between(Size(Key(3), Key(5)), 110000, 111000));--    dbfull()->TEST_CompactRange(0, NULL, NULL);-  }-}--TEST(DBTest, IteratorPinsRef) {-  Put("foo", "hello");--  // Get iterator that will yield the current contents of the DB.-  Iterator* iter = db_->NewIterator(ReadOptions());--  // Write to force compactions-  Put("foo", "newvalue1");-  for (int i = 0; i < 100; i++) {-    ASSERT_OK(Put(Key(i), Key(i) + std::string(100000, 'v'))); // 100K values-  }-  Put("foo", "newvalue2");--  iter->SeekToFirst();-  ASSERT_TRUE(iter->Valid());-  ASSERT_EQ("foo", iter->key().ToString());-  ASSERT_EQ("hello", iter->value().ToString());-  iter->Next();-  ASSERT_TRUE(!iter->Valid());-  delete iter;-}--TEST(DBTest, Snapshot) {-  Put("foo", "v1");-  const Snapshot* s1 = db_->GetSnapshot();-  Put("foo", "v2");-  const Snapshot* s2 = db_->GetSnapshot();-  Put("foo", "v3");-  const Snapshot* s3 = db_->GetSnapshot();--  Put("foo", "v4");-  ASSERT_EQ("v1", Get("foo", s1));-  ASSERT_EQ("v2", Get("foo", s2));-  ASSERT_EQ("v3", Get("foo", s3));-  ASSERT_EQ("v4", Get("foo"));--  db_->ReleaseSnapshot(s3);-  ASSERT_EQ("v1", Get("foo", s1));-  ASSERT_EQ("v2", Get("foo", s2));-  ASSERT_EQ("v4", Get("foo"));--  db_->ReleaseSnapshot(s1);-  ASSERT_EQ("v2", Get("foo", s2));-  ASSERT_EQ("v4", Get("foo"));--  db_->ReleaseSnapshot(s2);-  ASSERT_EQ("v4", Get("foo"));-}--TEST(DBTest, HiddenValuesAreRemoved) {-  Random rnd(301);-  FillLevels("a", "z");--  std::string big = RandomString(&rnd, 50000);-  Put("foo", big);-  Put("pastfoo", "v");-  const Snapshot* snapshot = db_->GetSnapshot();-  Put("foo", "tiny");-  Put("pastfoo2", "v2");        // Advance sequence number one more--  ASSERT_OK(dbfull()->TEST_CompactMemTable());-  ASSERT_GT(NumTableFilesAtLevel(0), 0);--  ASSERT_EQ(big, Get("foo", snapshot));-  ASSERT_TRUE(Between(Size("", "pastfoo"), 50000, 60000));-  db_->ReleaseSnapshot(snapshot);-  ASSERT_EQ(AllEntriesFor("foo"), "[ tiny, " + big + " ]");-  Slice x("x");-  dbfull()->TEST_CompactRange(0, NULL, &x);-  ASSERT_EQ(AllEntriesFor("foo"), "[ tiny ]");-  ASSERT_EQ(NumTableFilesAtLevel(0), 0);-  ASSERT_GE(NumTableFilesAtLevel(1), 1);-  dbfull()->TEST_CompactRange(1, NULL, &x);-  ASSERT_EQ(AllEntriesFor("foo"), "[ tiny ]");--  ASSERT_TRUE(Between(Size("", "pastfoo"), 0, 1000));-}--TEST(DBTest, DeletionMarkers1) {-  Put("foo", "v1");-  ASSERT_OK(dbfull()->TEST_CompactMemTable());-  const int last = config::kMaxMemCompactLevel;-  ASSERT_EQ(NumTableFilesAtLevel(last), 1);   // foo => v1 is now in last level--  // Place a table at level last-1 to prevent merging with preceding mutation-  Put("a", "begin");-  Put("z", "end");-  dbfull()->TEST_CompactMemTable();-  ASSERT_EQ(NumTableFilesAtLevel(last), 1);-  ASSERT_EQ(NumTableFilesAtLevel(last-1), 1);--  Delete("foo");-  Put("foo", "v2");-  ASSERT_EQ(AllEntriesFor("foo"), "[ v2, DEL, v1 ]");-  ASSERT_OK(dbfull()->TEST_CompactMemTable());  // Moves to level last-2-  ASSERT_EQ(AllEntriesFor("foo"), "[ v2, DEL, v1 ]");-  Slice z("z");-  dbfull()->TEST_CompactRange(last-2, NULL, &z);-  // DEL eliminated, but v1 remains because we aren't compacting that level-  // (DEL can be eliminated because v2 hides v1).-  ASSERT_EQ(AllEntriesFor("foo"), "[ v2, v1 ]");-  dbfull()->TEST_CompactRange(last-1, NULL, NULL);-  // Merging last-1 w/ last, so we are the base level for "foo", so-  // DEL is removed.  (as is v1).-  ASSERT_EQ(AllEntriesFor("foo"), "[ v2 ]");-}--TEST(DBTest, DeletionMarkers2) {-  Put("foo", "v1");-  ASSERT_OK(dbfull()->TEST_CompactMemTable());-  const int last = config::kMaxMemCompactLevel;-  ASSERT_EQ(NumTableFilesAtLevel(last), 1);   // foo => v1 is now in last level--  // Place a table at level last-1 to prevent merging with preceding mutation-  Put("a", "begin");-  Put("z", "end");-  dbfull()->TEST_CompactMemTable();-  ASSERT_EQ(NumTableFilesAtLevel(last), 1);-  ASSERT_EQ(NumTableFilesAtLevel(last-1), 1);--  Delete("foo");-  ASSERT_EQ(AllEntriesFor("foo"), "[ DEL, v1 ]");-  ASSERT_OK(dbfull()->TEST_CompactMemTable());  // Moves to level last-2-  ASSERT_EQ(AllEntriesFor("foo"), "[ DEL, v1 ]");-  dbfull()->TEST_CompactRange(last-2, NULL, NULL);-  // DEL kept: "last" file overlaps-  ASSERT_EQ(AllEntriesFor("foo"), "[ DEL, v1 ]");-  dbfull()->TEST_CompactRange(last-1, NULL, NULL);-  // Merging last-1 w/ last, so we are the base level for "foo", so-  // DEL is removed.  (as is v1).-  ASSERT_EQ(AllEntriesFor("foo"), "[ ]");-}--TEST(DBTest, OverlapInLevel0) {-  ASSERT_EQ(config::kMaxMemCompactLevel, 2) << "Fix test to match config";--  // Fill levels 1 and 2 to disable the pushing of new memtables to levels > 0.-  ASSERT_OK(Put("100", "v100"));-  ASSERT_OK(Put("999", "v999"));-  dbfull()->TEST_CompactMemTable();-  ASSERT_OK(Delete("100"));-  ASSERT_OK(Delete("999"));-  dbfull()->TEST_CompactMemTable();-  ASSERT_EQ("0,1,1", FilesPerLevel());--  // Make files spanning the following ranges in level-0:-  //  files[0]  200 .. 900-  //  files[1]  300 .. 500-  // Note that files are sorted by smallest key.-  ASSERT_OK(Put("300", "v300"));-  ASSERT_OK(Put("500", "v500"));-  dbfull()->TEST_CompactMemTable();-  ASSERT_OK(Put("200", "v200"));-  ASSERT_OK(Put("600", "v600"));-  ASSERT_OK(Put("900", "v900"));-  dbfull()->TEST_CompactMemTable();-  ASSERT_EQ("2,1,1", FilesPerLevel());--  // Compact away the placeholder files we created initially-  dbfull()->TEST_CompactRange(1, NULL, NULL);-  dbfull()->TEST_CompactRange(2, NULL, NULL);-  ASSERT_EQ("2", FilesPerLevel());--  // Do a memtable compaction.  Before bug-fix, the compaction would-  // not detect the overlap with level-0 files and would incorrectly place-  // the deletion in a deeper level.-  ASSERT_OK(Delete("600"));-  dbfull()->TEST_CompactMemTable();-  ASSERT_EQ("3", FilesPerLevel());-  ASSERT_EQ("NOT_FOUND", Get("600"));-}--TEST(DBTest, L0_CompactionBug_Issue44_a) {- Reopen();- ASSERT_OK(Put("b", "v"));- Reopen();- ASSERT_OK(Delete("b"));- ASSERT_OK(Delete("a"));- Reopen();- ASSERT_OK(Delete("a"));- Reopen();- ASSERT_OK(Put("a", "v"));- Reopen();- Reopen();- ASSERT_EQ("(a->v)", Contents());- env_->SleepForMicroseconds(1000000);  // Wait for compaction to finish- ASSERT_EQ("(a->v)", Contents());-}--TEST(DBTest, L0_CompactionBug_Issue44_b) {- Reopen();- Put("","");- Reopen();- Delete("e");- Put("","");- Reopen();- Put("c", "cv");- Reopen();- Put("","");- Reopen();- Put("","");- env_->SleepForMicroseconds(1000000);  // Wait for compaction to finish- Reopen();- Put("d","dv");- Reopen();- Put("","");- Reopen();- Delete("d");- Delete("b");- Reopen();- ASSERT_EQ("(->)(c->cv)", Contents());- env_->SleepForMicroseconds(1000000);  // Wait for compaction to finish- ASSERT_EQ("(->)(c->cv)", Contents());-}--TEST(DBTest, ComparatorCheck) {-  class NewComparator : public Comparator {-   public:-    virtual const char* Name() const { return "leveldb.NewComparator"; }-    virtual int Compare(const Slice& a, const Slice& b) const {-      return BytewiseComparator()->Compare(a, b);-    }-    virtual void FindShortestSeparator(std::string* s, const Slice& l) const {-      BytewiseComparator()->FindShortestSeparator(s, l);-    }-    virtual void FindShortSuccessor(std::string* key) const {-      BytewiseComparator()->FindShortSuccessor(key);-    }-  };-  NewComparator cmp;-  Options new_options;-  new_options.comparator = &cmp;-  Status s = TryReopen(&new_options);-  ASSERT_TRUE(!s.ok());-  ASSERT_TRUE(s.ToString().find("comparator") != std::string::npos)-      << s.ToString();-}--TEST(DBTest, CustomComparator) {-  class NumberComparator : public Comparator {-   public:-    virtual const char* Name() const { return "test.NumberComparator"; }-    virtual int Compare(const Slice& a, const Slice& b) const {-      return ToNumber(a) - ToNumber(b);-    }-    virtual void FindShortestSeparator(std::string* s, const Slice& l) const {-      ToNumber(*s);     // Check format-      ToNumber(l);      // Check format-    }-    virtual void FindShortSuccessor(std::string* key) const {-      ToNumber(*key);   // Check format-    }-   private:-    static int ToNumber(const Slice& x) {-      // Check that there are no extra characters.-      ASSERT_TRUE(x.size() >= 2 && x[0] == '[' && x[x.size()-1] == ']')-          << EscapeString(x);-      int val;-      char ignored;-      ASSERT_TRUE(sscanf(x.ToString().c_str(), "[%i]%c", &val, &ignored) == 1)-          << EscapeString(x);-      return val;-    }-  };-  NumberComparator cmp;-  Options new_options;-  new_options.create_if_missing = true;-  new_options.comparator = &cmp;-  new_options.write_buffer_size = 1000;  // Compact more often-  DestroyAndReopen(&new_options);-  ASSERT_OK(Put("[10]", "ten"));-  ASSERT_OK(Put("[0x14]", "twenty"));-  for (int i = 0; i < 2; i++) {-    ASSERT_EQ("ten", Get("[10]"));-    ASSERT_EQ("ten", Get("[0xa]"));-    ASSERT_EQ("twenty", Get("[20]"));-    ASSERT_EQ("twenty", Get("[0x14]"));-    Compact("[0]", "[9999]");-  }--  for (int run = 0; run < 2; run++) {-    for (int i = 0; i < 1000; i++) {-      char buf[100];-      snprintf(buf, sizeof(buf), "[%d]", i*10);-      ASSERT_OK(Put(buf, buf));-    }-    Compact("[0]", "[1000000]");-  }-}--TEST(DBTest, ManualCompaction) {-  ASSERT_EQ(config::kMaxMemCompactLevel, 2)-      << "Need to update this test to match kMaxMemCompactLevel";--  MakeTables(3, "p", "q");-  ASSERT_EQ("1,1,1", FilesPerLevel());--  // Compaction range falls before files-  Compact("", "c");-  ASSERT_EQ("1,1,1", FilesPerLevel());--  // Compaction range falls after files-  Compact("r", "z");-  ASSERT_EQ("1,1,1", FilesPerLevel());--  // Compaction range overlaps files-  Compact("p1", "p9");-  ASSERT_EQ("0,0,1", FilesPerLevel());--  // Populate a different range-  MakeTables(3, "c", "e");-  ASSERT_EQ("1,1,2", FilesPerLevel());--  // Compact just the new range-  Compact("b", "f");-  ASSERT_EQ("0,0,2", FilesPerLevel());--  // Compact all-  MakeTables(1, "a", "z");-  ASSERT_EQ("0,1,2", FilesPerLevel());-  db_->CompactRange(NULL, NULL);-  ASSERT_EQ("0,0,1", FilesPerLevel());-}--TEST(DBTest, DBOpen_Options) {-  std::string dbname = test::TmpDir() + "/db_options_test";-  DestroyDB(dbname, Options());--  // Does not exist, and create_if_missing == false: error-  DB* db = NULL;-  Options opts;-  opts.create_if_missing = false;-  Status s = DB::Open(opts, dbname, &db);-  ASSERT_TRUE(strstr(s.ToString().c_str(), "does not exist") != NULL);-  ASSERT_TRUE(db == NULL);--  // Does not exist, and create_if_missing == true: OK-  opts.create_if_missing = true;-  s = DB::Open(opts, dbname, &db);-  ASSERT_OK(s);-  ASSERT_TRUE(db != NULL);--  delete db;-  db = NULL;--  // Does exist, and error_if_exists == true: error-  opts.create_if_missing = false;-  opts.error_if_exists = true;-  s = DB::Open(opts, dbname, &db);-  ASSERT_TRUE(strstr(s.ToString().c_str(), "exists") != NULL);-  ASSERT_TRUE(db == NULL);--  // Does exist, and error_if_exists == false: OK-  opts.create_if_missing = true;-  opts.error_if_exists = false;-  s = DB::Open(opts, dbname, &db);-  ASSERT_OK(s);-  ASSERT_TRUE(db != NULL);--  delete db;-  db = NULL;-}--// Check that number of files does not grow when we are out of space-TEST(DBTest, NoSpace) {-  Options options;-  options.env = env_;-  Reopen(&options);--  ASSERT_OK(Put("foo", "v1"));-  ASSERT_EQ("v1", Get("foo"));-  Compact("a", "z");-  const int num_files = CountFiles();-  env_->no_space_.Release_Store(env_);   // Force out-of-space errors-  for (int i = 0; i < 10; i++) {-    for (int level = 0; level < config::kNumLevels-1; level++) {-      dbfull()->TEST_CompactRange(level, NULL, NULL);-    }-  }-  env_->no_space_.Release_Store(NULL);-  ASSERT_LT(CountFiles(), num_files + 5);-}--TEST(DBTest, FilesDeletedAfterCompaction) {-  ASSERT_OK(Put("foo", "v2"));-  Compact("a", "z");-  const int num_files = CountFiles();-  for (int i = 0; i < 10; i++) {-    ASSERT_OK(Put("foo", "v2"));-    Compact("a", "z");-  }-  ASSERT_EQ(CountFiles(), num_files);-}--// Multi-threaded test:-namespace {--static const int kNumThreads = 4;-static const int kTestSeconds = 10;-static const int kNumKeys = 1000;--struct MTState {-  DBTest* test;-  port::AtomicPointer stop;-  port::AtomicPointer counter[kNumThreads];-  port::AtomicPointer thread_done[kNumThreads];-};--struct MTThread {-  MTState* state;-  int id;-};--static void MTThreadBody(void* arg) {-  MTThread* t = reinterpret_cast<MTThread*>(arg);-  int id = t->id;-  DB* db = t->state->test->db_;-  uintptr_t counter = 0;-  fprintf(stderr, "... starting thread %d\n", id);-  Random rnd(1000 + id);-  std::string value;-  char valbuf[1500];-  while (t->state->stop.Acquire_Load() == NULL) {-    t->state->counter[id].Release_Store(reinterpret_cast<void*>(counter));--    int key = rnd.Uniform(kNumKeys);-    char keybuf[20];-    snprintf(keybuf, sizeof(keybuf), "%016d", key);--    if (rnd.OneIn(2)) {-      // Write values of the form <key, my id, counter>.-      // We add some padding for force compactions.-      snprintf(valbuf, sizeof(valbuf), "%d.%d.%-1000d",-               key, id, static_cast<int>(counter));-      ASSERT_OK(db->Put(WriteOptions(), Slice(keybuf), Slice(valbuf)));-    } else {-      // Read a value and verify that it matches the pattern written above.-      Status s = db->Get(ReadOptions(), Slice(keybuf), &value);-      if (s.IsNotFound()) {-        // Key has not yet been written-      } else {-        // Check that the writer thread counter is >= the counter in the value-        ASSERT_OK(s);-        int k, w, c;-        ASSERT_EQ(3, sscanf(value.c_str(), "%d.%d.%d", &k, &w, &c)) << value;-        ASSERT_EQ(k, key);-        ASSERT_GE(w, 0);-        ASSERT_LT(w, kNumThreads);-        ASSERT_LE(c, reinterpret_cast<uintptr_t>(-            t->state->counter[w].Acquire_Load()));-      }-    }-    counter++;-  }-  t->state->thread_done[id].Release_Store(t);-  fprintf(stderr, "... stopping thread %d after %d ops\n", id, int(counter));-}--}  // namespace--TEST(DBTest, MultiThreaded) {-  // Initialize state-  MTState mt;-  mt.test = this;-  mt.stop.Release_Store(0);-  for (int id = 0; id < kNumThreads; id++) {-    mt.counter[id].Release_Store(0);-    mt.thread_done[id].Release_Store(0);-  }--  // Start threads-  MTThread thread[kNumThreads];-  for (int id = 0; id < kNumThreads; id++) {-    thread[id].state = &mt;-    thread[id].id = id;-    env_->StartThread(MTThreadBody, &thread[id]);-  }--  // Let them run for a while-  env_->SleepForMicroseconds(kTestSeconds * 1000000);--  // Stop the threads and wait for them to finish-  mt.stop.Release_Store(&mt);-  for (int id = 0; id < kNumThreads; id++) {-    while (mt.thread_done[id].Acquire_Load() == NULL) {-      env_->SleepForMicroseconds(100000);-    }-  }-}--namespace {-typedef std::map<std::string, std::string> KVMap;-}--class ModelDB: public DB {- public:-  class ModelSnapshot : public Snapshot {-   public:-    KVMap map_;-  };--  explicit ModelDB(const Options& options): options_(options) { }-  ~ModelDB() { }-  virtual Status Put(const WriteOptions& o, const Slice& k, const Slice& v) {-    return DB::Put(o, k, v);-  }-  virtual Status Delete(const WriteOptions& o, const Slice& key) {-    return DB::Delete(o, key);-  }-  virtual Status Get(const ReadOptions& options,-                     const Slice& key, std::string* value) {-    assert(false);      // Not implemented-    return Status::NotFound(key);-  }-  virtual Iterator* NewIterator(const ReadOptions& options) {-    if (options.snapshot == NULL) {-      KVMap* saved = new KVMap;-      *saved = map_;-      return new ModelIter(saved, true);-    } else {-      const KVMap* snapshot_state =-          &(reinterpret_cast<const ModelSnapshot*>(options.snapshot)->map_);-      return new ModelIter(snapshot_state, false);-    }-  }-  virtual const Snapshot* GetSnapshot() {-    ModelSnapshot* snapshot = new ModelSnapshot;-    snapshot->map_ = map_;-    return snapshot;-  }--  virtual void ReleaseSnapshot(const Snapshot* snapshot) {-    delete reinterpret_cast<const ModelSnapshot*>(snapshot);-  }-  virtual Status Write(const WriteOptions& options, WriteBatch* batch) {-    class Handler : public WriteBatch::Handler {-     public:-      KVMap* map_;-      virtual void Put(const Slice& key, const Slice& value) {-        (*map_)[key.ToString()] = value.ToString();-      }-      virtual void Delete(const Slice& key) {-        map_->erase(key.ToString());-      }-    };-    Handler handler;-    handler.map_ = &map_;-    return batch->Iterate(&handler);-  }--  virtual bool GetProperty(const Slice& property, std::string* value) {-    return false;-  }-  virtual void GetApproximateSizes(const Range* r, int n, uint64_t* sizes) {-    for (int i = 0; i < n; i++) {-      sizes[i] = 0;-    }-  }-  virtual void CompactRange(const Slice* start, const Slice* end) {-  }-- private:-  class ModelIter: public Iterator {-   public:-    ModelIter(const KVMap* map, bool owned)-        : map_(map), owned_(owned), iter_(map_->end()) {-    }-    ~ModelIter() {-      if (owned_) delete map_;-    }-    virtual bool Valid() const { return iter_ != map_->end(); }-    virtual void SeekToFirst() { iter_ = map_->begin(); }-    virtual void SeekToLast() {-      if (map_->empty()) {-        iter_ = map_->end();-      } else {-        iter_ = map_->find(map_->rbegin()->first);-      }-    }-    virtual void Seek(const Slice& k) {-      iter_ = map_->lower_bound(k.ToString());-    }-    virtual void Next() { ++iter_; }-    virtual void Prev() { --iter_; }-    virtual Slice key() const { return iter_->first; }-    virtual Slice value() const { return iter_->second; }-    virtual Status status() const { return Status::OK(); }-   private:-    const KVMap* const map_;-    const bool owned_;  // Do we own map_-    KVMap::const_iterator iter_;-  };-  const Options options_;-  KVMap map_;-};--static std::string RandomKey(Random* rnd) {-  int len = (rnd->OneIn(3)-             ? 1                // Short sometimes to encourage collisions-             : (rnd->OneIn(100) ? rnd->Skewed(10) : rnd->Uniform(10)));-  return test::RandomKey(rnd, len);-}--static bool CompareIterators(int step,-                             DB* model,-                             DB* db,-                             const Snapshot* model_snap,-                             const Snapshot* db_snap) {-  ReadOptions options;-  options.snapshot = model_snap;-  Iterator* miter = model->NewIterator(options);-  options.snapshot = db_snap;-  Iterator* dbiter = db->NewIterator(options);-  bool ok = true;-  int count = 0;-  for (miter->SeekToFirst(), dbiter->SeekToFirst();-       ok && miter->Valid() && dbiter->Valid();-       miter->Next(), dbiter->Next()) {-    count++;-    if (miter->key().compare(dbiter->key()) != 0) {-      fprintf(stderr, "step %d: Key mismatch: '%s' vs. '%s'\n",-              step,-              EscapeString(miter->key()).c_str(),-              EscapeString(dbiter->key()).c_str());-      ok = false;-      break;-    }--    if (miter->value().compare(dbiter->value()) != 0) {-      fprintf(stderr, "step %d: Value mismatch for key '%s': '%s' vs. '%s'\n",-              step,-              EscapeString(miter->key()).c_str(),-              EscapeString(miter->value()).c_str(),-              EscapeString(miter->value()).c_str());-      ok = false;-    }-  }--  if (ok) {-    if (miter->Valid() != dbiter->Valid()) {-      fprintf(stderr, "step %d: Mismatch at end of iterators: %d vs. %d\n",-              step, miter->Valid(), dbiter->Valid());-      ok = false;-    }-  }-  fprintf(stderr, "%d entries compared: ok=%d\n", count, ok);-  delete miter;-  delete dbiter;-  return ok;-}--TEST(DBTest, Randomized) {-  Random rnd(test::RandomSeed());-  ModelDB model(last_options_);-  const int N = 10000;-  const Snapshot* model_snap = NULL;-  const Snapshot* db_snap = NULL;-  std::string k, v;-  for (int step = 0; step < N; step++) {-    if (step % 100 == 0) {-      fprintf(stderr, "Step %d of %d\n", step, N);-    }-    int p = rnd.Uniform(100);-    if (p < 45) {                               // Put-      k = RandomKey(&rnd);-      v = RandomString(&rnd,-                       rnd.OneIn(20)-                       ? 100 + rnd.Uniform(100)-                       : rnd.Uniform(8));-      ASSERT_OK(model.Put(WriteOptions(), k, v));-      ASSERT_OK(db_->Put(WriteOptions(), k, v));--    } else if (p < 90) {                        // Delete-      k = RandomKey(&rnd);-      ASSERT_OK(model.Delete(WriteOptions(), k));-      ASSERT_OK(db_->Delete(WriteOptions(), k));---    } else {                                    // Multi-element batch-      WriteBatch b;-      const int num = rnd.Uniform(8);-      for (int i = 0; i < num; i++) {-        if (i == 0 || !rnd.OneIn(10)) {-          k = RandomKey(&rnd);-        } else {-          // Periodically re-use the same key from the previous iter, so-          // we have multiple entries in the write batch for the same key-        }-        if (rnd.OneIn(2)) {-          v = RandomString(&rnd, rnd.Uniform(10));-          b.Put(k, v);-        } else {-          b.Delete(k);-        }-      }-      ASSERT_OK(model.Write(WriteOptions(), &b));-      ASSERT_OK(db_->Write(WriteOptions(), &b));-    }--    if ((step % 100) == 0) {-      ASSERT_TRUE(CompareIterators(step, &model, db_, NULL, NULL));-      ASSERT_TRUE(CompareIterators(step, &model, db_, model_snap, db_snap));-      // Save a snapshot from each DB this time that we'll use next-      // time we compare things, to make sure the current state is-      // preserved with the snapshot-      if (model_snap != NULL) model.ReleaseSnapshot(model_snap);-      if (db_snap != NULL) db_->ReleaseSnapshot(db_snap);--      Reopen();-      ASSERT_TRUE(CompareIterators(step, &model, db_, NULL, NULL));--      model_snap = model.GetSnapshot();-      db_snap = db_->GetSnapshot();-    }-  }-  if (model_snap != NULL) model.ReleaseSnapshot(model_snap);-  if (db_snap != NULL) db_->ReleaseSnapshot(db_snap);-}--std::string MakeKey(unsigned int num) {-  char buf[30];-  snprintf(buf, sizeof(buf), "%016u", num);-  return std::string(buf);-}--void BM_LogAndApply(int iters, int num_base_files) {-  std::string dbname = test::TmpDir() + "/leveldb_test_benchmark";-  DestroyDB(dbname, Options());--  DB* db = NULL;-  Options opts;-  opts.create_if_missing = true;-  Status s = DB::Open(opts, dbname, &db);-  ASSERT_OK(s);-  ASSERT_TRUE(db != NULL);--  delete db;-  db = NULL;--  Env* env = Env::Default();--  port::Mutex mu;-  MutexLock l(&mu);--  InternalKeyComparator cmp(BytewiseComparator());-  Options options;-  VersionSet vset(dbname, &options, NULL, &cmp);-  ASSERT_OK(vset.Recover());-  VersionEdit vbase;-  uint64_t fnum = 1;-  for (int i = 0; i < num_base_files; i++) {-    InternalKey start(MakeKey(2*fnum), 1, kTypeValue);-    InternalKey limit(MakeKey(2*fnum+1), 1, kTypeDeletion);-    vbase.AddFile(2, fnum++, 1 /* file size */, start, limit);-  }-  ASSERT_OK(vset.LogAndApply(&vbase, &mu));--  uint64_t start_micros = env->NowMicros();--  for (int i = 0; i < iters; i++) {-    VersionEdit vedit;-    vedit.DeleteFile(2, fnum);-    InternalKey start(MakeKey(2*fnum), 1, kTypeValue);-    InternalKey limit(MakeKey(2*fnum+1), 1, kTypeDeletion);-    vedit.AddFile(2, fnum++, 1 /* file size */, start, limit);-    vset.LogAndApply(&vedit, &mu);-  }-  uint64_t stop_micros = env->NowMicros();-  unsigned int us = stop_micros - start_micros;-  char buf[16];-  snprintf(buf, sizeof(buf), "%d", num_base_files);-  fprintf(stderr,-          "BM_LogAndApply/%-6s   %8d iters : %9u us (%7.0f us / iter)\n",-          buf, iters, us, ((float)us) / iters);-}--}  // namespace leveldb--int main(int argc, char** argv) {-  if (argc > 1 && std::string(argv[1]) == "--benchmark") {-    leveldb::BM_LogAndApply(1000, 1);-    leveldb::BM_LogAndApply(1000, 100);-    leveldb::BM_LogAndApply(1000, 10000);-    leveldb::BM_LogAndApply(100, 100000);-    return 0;-  }--  return leveldb::test::RunAllTests();-}

@@ -1,120 +0,0 @@-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.-// Use of this source code is governed by a BSD-style license that can be-// found in the LICENSE file. See the AUTHORS file for names of contributors.--#include <stdio.h>-#include "db/dbformat.h"-#include "port/port.h"-#include "util/coding.h"--namespace leveldb {--static uint64_t PackSequenceAndType(uint64_t seq, ValueType t) {-  assert(seq <= kMaxSequenceNumber);-  assert(t <= kValueTypeForSeek);-  return (seq << 8) | t;-}--void AppendInternalKey(std::string* result, const ParsedInternalKey& key) {-  result->append(key.user_key.data(), key.user_key.size());-  PutFixed64(result, PackSequenceAndType(key.sequence, key.type));-}--std::string ParsedInternalKey::DebugString() const {-  char buf[50];-  snprintf(buf, sizeof(buf), "' @ %llu : %d",-           (unsigned long long) sequence,-           int(type));-  std::string result = "'";-  result += user_key.ToString();-  result += buf;-  return result;-}--std::string InternalKey::DebugString() const {-  std::string result;-  ParsedInternalKey parsed;-  if (ParseInternalKey(rep_, &parsed)) {-    result = parsed.DebugString();-  } else {-    result = "(bad)";-    result.append(EscapeString(rep_));-  }-  return result;-}--const char* InternalKeyComparator::Name() const {-  return "leveldb.InternalKeyComparator";-}--int InternalKeyComparator::Compare(const Slice& akey, const Slice& bkey) const {-  // Order by:-  //    increasing user key (according to user-supplied comparator)-  //    decreasing sequence number-  //    decreasing type (though sequence# should be enough to disambiguate)-  int r = user_comparator_->Compare(ExtractUserKey(akey), ExtractUserKey(bkey));-  if (r == 0) {-    const uint64_t anum = DecodeFixed64(akey.data() + akey.size() - 8);-    const uint64_t bnum = DecodeFixed64(bkey.data() + bkey.size() - 8);-    if (anum > bnum) {-      r = -1;-    } else if (anum < bnum) {-      r = +1;-    }-  }-  return r;-}--void InternalKeyComparator::FindShortestSeparator(-      std::string* start,-      const Slice& limit) const {-  // Attempt to shorten the user portion of the key-  Slice user_start = ExtractUserKey(*start);-  Slice user_limit = ExtractUserKey(limit);-  std::string tmp(user_start.data(), user_start.size());-  user_comparator_->FindShortestSeparator(&tmp, user_limit);-  if (tmp.size() < user_start.size() &&-      user_comparator_->Compare(user_start, tmp) < 0) {-    // User key has become shorter physically, but larger logically.-    // Tack on the earliest possible number to the shortened user key.-    PutFixed64(&tmp, PackSequenceAndType(kMaxSequenceNumber,kValueTypeForSeek));-    assert(this->Compare(*start, tmp) < 0);-    assert(this->Compare(tmp, limit) < 0);-    start->swap(tmp);-  }-}--void InternalKeyComparator::FindShortSuccessor(std::string* key) const {-  Slice user_key = ExtractUserKey(*key);-  std::string tmp(user_key.data(), user_key.size());-  user_comparator_->FindShortSuccessor(&tmp);-  if (tmp.size() < user_key.size() &&-      user_comparator_->Compare(user_key, tmp) < 0) {-    // User key has become shorter physically, but larger logically.-    // Tack on the earliest possible number to the shortened user key.-    PutFixed64(&tmp, PackSequenceAndType(kMaxSequenceNumber,kValueTypeForSeek));-    assert(this->Compare(*key, tmp) < 0);-    key->swap(tmp);-  }-}--LookupKey::LookupKey(const Slice& user_key, SequenceNumber s) {-  size_t usize = user_key.size();-  size_t needed = usize + 13;  // A conservative estimate-  char* dst;-  if (needed <= sizeof(space_)) {-    dst = space_;-  } else {-    dst = new char[needed];-  }-  start_ = dst;-  dst = EncodeVarint32(dst, usize + 8);-  kstart_ = dst;-  memcpy(dst, user_key.data(), usize);-  dst += usize;-  EncodeFixed64(dst, PackSequenceAndType(s, kValueTypeForSeek));-  dst += 8;-  end_ = dst;-}--}  // namespace leveldb

@@ -1,215 +0,0 @@-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.-// Use of this source code is governed by a BSD-style license that can be-// found in the LICENSE file. See the AUTHORS file for names of contributors.--#ifndef STORAGE_LEVELDB_DB_FORMAT_H_-#define STORAGE_LEVELDB_DB_FORMAT_H_--#include <stdio.h>-#include "leveldb/comparator.h"-#include "leveldb/db.h"-#include "leveldb/slice.h"-#include "leveldb/table_builder.h"-#include "util/coding.h"-#include "util/logging.h"--namespace leveldb {--// Grouping of constants.  We may want to make some of these-// parameters set via options.-namespace config {-static const int kNumLevels = 7;--// Level-0 compaction is started when we hit this many files.-static const int kL0_CompactionTrigger = 4;--// Soft limit on number of level-0 files.  We slow down writes at this point.-static const int kL0_SlowdownWritesTrigger = 8;--// Maximum number of level-0 files.  We stop writes at this point.-static const int kL0_StopWritesTrigger = 12;--// Maximum level to which a new compacted memtable is pushed if it-// does not create overlap.  We try to push to level 2 to avoid the-// relatively expensive level 0=>1 compactions and to avoid some-// expensive manifest file operations.  We do not push all the way to-// the largest level since that can generate a lot of wasted disk-// space if the same key space is being repeatedly overwritten.-static const int kMaxMemCompactLevel = 2;--}  // namespace config--class InternalKey;--// Value types encoded as the last component of internal keys.-// DO NOT CHANGE THESE ENUM VALUES: they are embedded in the on-disk-// data structures.-enum ValueType {-  kTypeDeletion = 0x0,-  kTypeValue = 0x1-};-// kValueTypeForSeek defines the ValueType that should be passed when-// constructing a ParsedInternalKey object for seeking to a particular-// sequence number (since we sort sequence numbers in decreasing order-// and the value type is embedded as the low 8 bits in the sequence-// number in internal keys, we need to use the highest-numbered-// ValueType, not the lowest).-static const ValueType kValueTypeForSeek = kTypeValue;--typedef uint64_t SequenceNumber;--// We leave eight bits empty at the bottom so a type and sequence#-// can be packed together into 64-bits.-static const SequenceNumber kMaxSequenceNumber =-    ((0x1ull << 56) - 1);--struct ParsedInternalKey {-  Slice user_key;-  SequenceNumber sequence;-  ValueType type;--  ParsedInternalKey() { }  // Intentionally left uninitialized (for speed)-  ParsedInternalKey(const Slice& u, const SequenceNumber& seq, ValueType t)-      : user_key(u), sequence(seq), type(t) { }-  std::string DebugString() const;-};--// Return the length of the encoding of "key".-inline size_t InternalKeyEncodingLength(const ParsedInternalKey& key) {-  return key.user_key.size() + 8;-}--// Append the serialization of "key" to *result.-extern void AppendInternalKey(std::string* result,-                              const ParsedInternalKey& key);--// Attempt to parse an internal key from "internal_key".  On success,-// stores the parsed data in "*result", and returns true.-//-// On error, returns false, leaves "*result" in an undefined state.-extern bool ParseInternalKey(const Slice& internal_key,-                             ParsedInternalKey* result);--// Returns the user key portion of an internal key.-inline Slice ExtractUserKey(const Slice& internal_key) {-  assert(internal_key.size() >= 8);-  return Slice(internal_key.data(), internal_key.size() - 8);-}--inline ValueType ExtractValueType(const Slice& internal_key) {-  assert(internal_key.size() >= 8);-  const size_t n = internal_key.size();-  uint64_t num = DecodeFixed64(internal_key.data() + n - 8);-  unsigned char c = num & 0xff;-  return static_cast<ValueType>(c);-}--// A comparator for internal keys that uses a specified comparator for-// the user key portion and breaks ties by decreasing sequence number.-class InternalKeyComparator : public Comparator {- private:-  const Comparator* user_comparator_;- public:-  explicit InternalKeyComparator(const Comparator* c) : user_comparator_(c) { }-  virtual const char* Name() const;-  virtual int Compare(const Slice& a, const Slice& b) const;-  virtual void FindShortestSeparator(-      std::string* start,-      const Slice& limit) const;-  virtual void FindShortSuccessor(std::string* key) const;--  const Comparator* user_comparator() const { return user_comparator_; }--  int Compare(const InternalKey& a, const InternalKey& b) const;-};--// Modules in this directory should keep internal keys wrapped inside-// the following class instead of plain strings so that we do not-// incorrectly use string comparisons instead of an InternalKeyComparator.-class InternalKey {- private:-  std::string rep_;- public:-  InternalKey() { }   // Leave rep_ as empty to indicate it is invalid-  InternalKey(const Slice& user_key, SequenceNumber s, ValueType t) {-    AppendInternalKey(&rep_, ParsedInternalKey(user_key, s, t));-  }--  void DecodeFrom(const Slice& s) { rep_.assign(s.data(), s.size()); }-  Slice Encode() const {-    assert(!rep_.empty());-    return rep_;-  }--  Slice user_key() const { return ExtractUserKey(rep_); }--  void SetFrom(const ParsedInternalKey& p) {-    rep_.clear();-    AppendInternalKey(&rep_, p);-  }--  void Clear() { rep_.clear(); }--  std::string DebugString() const;-};--inline int InternalKeyComparator::Compare(-    const InternalKey& a, const InternalKey& b) const {-  return Compare(a.Encode(), b.Encode());-}--inline bool ParseInternalKey(const Slice& internal_key,-                             ParsedInternalKey* result) {-  const size_t n = internal_key.size();-  if (n < 8) return false;-  uint64_t num = DecodeFixed64(internal_key.data() + n - 8);-  unsigned char c = num & 0xff;-  result->sequence = num >> 8;-  result->type = static_cast<ValueType>(c);-  result->user_key = Slice(internal_key.data(), n - 8);-  return (c <= static_cast<unsigned char>(kTypeValue));-}--// A helper class useful for DBImpl::Get()-class LookupKey {- public:-  // Initialize *this for looking up user_key at a snapshot with-  // the specified sequence number.-  LookupKey(const Slice& user_key, SequenceNumber sequence);--  ~LookupKey();--  // Return a key suitable for lookup in a MemTable.-  Slice memtable_key() const { return Slice(start_, end_ - start_); }--  // Return an internal key (suitable for passing to an internal iterator)-  Slice internal_key() const { return Slice(kstart_, end_ - kstart_); }--  // Return the user key-  Slice user_key() const { return Slice(kstart_, end_ - kstart_ - 8); }-- private:-  // We construct a char array of the form:-  //    klength  varint32               <-- start_-  //    userkey  char[klength]          <-- kstart_-  //    tag      uint64-  //                                    <-- end_-  // The array is a suitable MemTable key.-  // The suffix starting with "userkey" can be used as an InternalKey.-  const char* start_;-  const char* kstart_;-  const char* end_;-  char space_[200];      // Avoid allocation for short keys--  // No copying allowed-  LookupKey(const LookupKey&);-  void operator=(const LookupKey&);-};--inline LookupKey::~LookupKey() {-  if (start_ != space_) delete[] start_;-}--}  // namespace leveldb--#endif  // STORAGE_LEVELDB_DB_FORMAT_H_

@@ -1,112 +0,0 @@-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.-// Use of this source code is governed by a BSD-style license that can be-// found in the LICENSE file. See the AUTHORS file for names of contributors.--#include "db/dbformat.h"-#include "util/logging.h"-#include "util/testharness.h"--namespace leveldb {--static std::string IKey(const std::string& user_key,-                        uint64_t seq,-                        ValueType vt) {-  std::string encoded;-  AppendInternalKey(&encoded, ParsedInternalKey(user_key, seq, vt));-  return encoded;-}--static std::string Shorten(const std::string& s, const std::string& l) {-  std::string result = s;-  InternalKeyComparator(BytewiseComparator()).FindShortestSeparator(&result, l);-  return result;-}--static std::string ShortSuccessor(const std::string& s) {-  std::string result = s;-  InternalKeyComparator(BytewiseComparator()).FindShortSuccessor(&result);-  return result;-}--static void TestKey(const std::string& key,-                    uint64_t seq,-                    ValueType vt) {-  std::string encoded = IKey(key, seq, vt);--  Slice in(encoded);-  ParsedInternalKey decoded("", 0, kTypeValue);--  ASSERT_TRUE(ParseInternalKey(in, &decoded));-  ASSERT_EQ(key, decoded.user_key.ToString());-  ASSERT_EQ(seq, decoded.sequence);-  ASSERT_EQ(vt, decoded.type);--  ASSERT_TRUE(!ParseInternalKey(Slice("bar"), &decoded));-}--class FormatTest { };--TEST(FormatTest, InternalKey_EncodeDecode) {-  const char* keys[] = { "", "k", "hello", "longggggggggggggggggggggg" };-  const uint64_t seq[] = {-    1, 2, 3,-    (1ull << 8) - 1, 1ull << 8, (1ull << 8) + 1,-    (1ull << 16) - 1, 1ull << 16, (1ull << 16) + 1,-    (1ull << 32) - 1, 1ull << 32, (1ull << 32) + 1-  };-  for (int k = 0; k < sizeof(keys) / sizeof(keys[0]); k++) {-    for (int s = 0; s < sizeof(seq) / sizeof(seq[0]); s++) {-      TestKey(keys[k], seq[s], kTypeValue);-      TestKey("hello", 1, kTypeDeletion);-    }-  }-}--TEST(FormatTest, InternalKeyShortSeparator) {-  // When user keys are same-  ASSERT_EQ(IKey("foo", 100, kTypeValue),-            Shorten(IKey("foo", 100, kTypeValue),-                    IKey("foo", 99, kTypeValue)));-  ASSERT_EQ(IKey("foo", 100, kTypeValue),-            Shorten(IKey("foo", 100, kTypeValue),-                    IKey("foo", 101, kTypeValue)));-  ASSERT_EQ(IKey("foo", 100, kTypeValue),-            Shorten(IKey("foo", 100, kTypeValue),-                    IKey("foo", 100, kTypeValue)));-  ASSERT_EQ(IKey("foo", 100, kTypeValue),-            Shorten(IKey("foo", 100, kTypeValue),-                    IKey("foo", 100, kTypeDeletion)));--  // When user keys are misordered-  ASSERT_EQ(IKey("foo", 100, kTypeValue),-            Shorten(IKey("foo", 100, kTypeValue),-                    IKey("bar", 99, kTypeValue)));--  // When user keys are different, but correctly ordered-  ASSERT_EQ(IKey("g", kMaxSequenceNumber, kValueTypeForSeek),-            Shorten(IKey("foo", 100, kTypeValue),-                    IKey("hello", 200, kTypeValue)));--  // When start user key is prefix of limit user key-  ASSERT_EQ(IKey("foo", 100, kTypeValue),-            Shorten(IKey("foo", 100, kTypeValue),-                    IKey("foobar", 200, kTypeValue)));--  // When limit user key is prefix of start user key-  ASSERT_EQ(IKey("foobar", 100, kTypeValue),-            Shorten(IKey("foobar", 100, kTypeValue),-                    IKey("foo", 200, kTypeValue)));-}--TEST(FormatTest, InternalKeyShortestSuccessor) {-  ASSERT_EQ(IKey("g", kMaxSequenceNumber, kValueTypeForSeek),-            ShortSuccessor(IKey("foo", 100, kTypeValue)));-  ASSERT_EQ(IKey("\xff\xff", 100, kTypeValue),-            ShortSuccessor(IKey("\xff\xff", 100, kTypeValue)));-}--}  // namespace leveldb--int main(int argc, char** argv) {-  return leveldb::test::RunAllTests();-}

@@ -1,139 +0,0 @@-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.-// Use of this source code is governed by a BSD-style license that can be-// found in the LICENSE file. See the AUTHORS file for names of contributors.--#include <ctype.h>-#include <stdio.h>-#include "db/filename.h"-#include "db/dbformat.h"-#include "leveldb/env.h"-#include "util/logging.h"--namespace leveldb {--// A utility routine: write "data" to the named file and Sync() it.-extern Status WriteStringToFileSync(Env* env, const Slice& data,-                                    const std::string& fname);--static std::string MakeFileName(const std::string& name, uint64_t number,-                                const char* suffix) {-  char buf[100];-  snprintf(buf, sizeof(buf), "/%06llu.%s",-           static_cast<unsigned long long>(number),-           suffix);-  return name + buf;-}--std::string LogFileName(const std::string& name, uint64_t number) {-  assert(number > 0);-  return MakeFileName(name, number, "log");-}--std::string TableFileName(const std::string& name, uint64_t number) {-  assert(number > 0);-  return MakeFileName(name, number, "sst");-}--std::string DescriptorFileName(const std::string& dbname, uint64_t number) {-  assert(number > 0);-  char buf[100];-  snprintf(buf, sizeof(buf), "/MANIFEST-%06llu",-           static_cast<unsigned long long>(number));-  return dbname + buf;-}--std::string CurrentFileName(const std::string& dbname) {-  return dbname + "/CURRENT";-}--std::string LockFileName(const std::string& dbname) {-  return dbname + "/LOCK";-}--std::string TempFileName(const std::string& dbname, uint64_t number) {-  assert(number > 0);-  return MakeFileName(dbname, number, "dbtmp");-}--std::string InfoLogFileName(const std::string& dbname) {-  return dbname + "/LOG";-}--// Return the name of the old info log file for "dbname".-std::string OldInfoLogFileName(const std::string& dbname) {-  return dbname + "/LOG.old";-}---// Owned filenames have the form:-//    dbname/CURRENT-//    dbname/LOCK-//    dbname/LOG-//    dbname/LOG.old-//    dbname/MANIFEST-[0-9]+-//    dbname/[0-9]+.(log|sst)-bool ParseFileName(const std::string& fname,-                   uint64_t* number,-                   FileType* type) {-  Slice rest(fname);-  if (rest == "CURRENT") {-    *number = 0;-    *type = kCurrentFile;-  } else if (rest == "LOCK") {-    *number = 0;-    *type = kDBLockFile;-  } else if (rest == "LOG" || rest == "LOG.old") {-    *number = 0;-    *type = kInfoLogFile;-  } else if (rest.starts_with("MANIFEST-")) {-    rest.remove_prefix(strlen("MANIFEST-"));-    uint64_t num;-    if (!ConsumeDecimalNumber(&rest, &num)) {-      return false;-    }-    if (!rest.empty()) {-      return false;-    }-    *type = kDescriptorFile;-    *number = num;-  } else {-    // Avoid strtoull() to keep filename format independent of the-    // current locale-    uint64_t num;-    if (!ConsumeDecimalNumber(&rest, &num)) {-      return false;-    }-    Slice suffix = rest;-    if (suffix == Slice(".log")) {-      *type = kLogFile;-    } else if (suffix == Slice(".sst")) {-      *type = kTableFile;-    } else if (suffix == Slice(".dbtmp")) {-      *type = kTempFile;-    } else {-      return false;-    }-    *number = num;-  }-  return true;-}--Status SetCurrentFile(Env* env, const std::string& dbname,-                      uint64_t descriptor_number) {-  // Remove leading "dbname/" and add newline to manifest file name-  std::string manifest = DescriptorFileName(dbname, descriptor_number);-  Slice contents = manifest;-  assert(contents.starts_with(dbname + "/"));-  contents.remove_prefix(dbname.size() + 1);-  std::string tmp = TempFileName(dbname, descriptor_number);-  Status s = WriteStringToFileSync(env, contents.ToString() + "\n", tmp);-  if (s.ok()) {-    s = env->RenameFile(tmp, CurrentFileName(dbname));-  }-  if (!s.ok()) {-    env->DeleteFile(tmp);-  }-  return s;-}--}  // namespace leveldb

@@ -1,80 +0,0 @@-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.-// Use of this source code is governed by a BSD-style license that can be-// found in the LICENSE file. See the AUTHORS file for names of contributors.-//-// File names used by DB code--#ifndef STORAGE_LEVELDB_DB_FILENAME_H_-#define STORAGE_LEVELDB_DB_FILENAME_H_--#include <stdint.h>-#include <string>-#include "leveldb/slice.h"-#include "leveldb/status.h"-#include "port/port.h"--namespace leveldb {--class Env;--enum FileType {-  kLogFile,-  kDBLockFile,-  kTableFile,-  kDescriptorFile,-  kCurrentFile,-  kTempFile,-  kInfoLogFile  // Either the current one, or an old one-};--// Return the name of the log file with the specified number-// in the db named by "dbname".  The result will be prefixed with-// "dbname".-extern std::string LogFileName(const std::string& dbname, uint64_t number);--// Return the name of the sstable with the specified number-// in the db named by "dbname".  The result will be prefixed with-// "dbname".-extern std::string TableFileName(const std::string& dbname, uint64_t number);--// Return the name of the descriptor file for the db named by-// "dbname" and the specified incarnation number.  The result will be-// prefixed with "dbname".-extern std::string DescriptorFileName(const std::string& dbname,-                                      uint64_t number);--// Return the name of the current file.  This file contains the name-// of the current manifest file.  The result will be prefixed with-// "dbname".-extern std::string CurrentFileName(const std::string& dbname);--// Return the name of the lock file for the db named by-// "dbname".  The result will be prefixed with "dbname".-extern std::string LockFileName(const std::string& dbname);--// Return the name of a temporary file owned by the db named "dbname".-// The result will be prefixed with "dbname".-extern std::string TempFileName(const std::string& dbname, uint64_t number);--// Return the name of the info log file for "dbname".-extern std::string InfoLogFileName(const std::string& dbname);--// Return the name of the old info log file for "dbname".-extern std::string OldInfoLogFileName(const std::string& dbname);--// If filename is a leveldb file, store the type of the file in *type.-// The number encoded in the filename is stored in *number.  If the-// filename was successfully parsed, returns true.  Else return false.-extern bool ParseFileName(const std::string& filename,-                          uint64_t* number,-                          FileType* type);--// Make the CURRENT file point to the descriptor file with the-// specified number.-extern Status SetCurrentFile(Env* env, const std::string& dbname,-                             uint64_t descriptor_number);---}  // namespace leveldb--#endif  // STORAGE_LEVELDB_DB_FILENAME_H_

@@ -1,122 +0,0 @@-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.-// Use of this source code is governed by a BSD-style license that can be-// found in the LICENSE file. See the AUTHORS file for names of contributors.--#include "db/filename.h"--#include "db/dbformat.h"-#include "port/port.h"-#include "util/logging.h"-#include "util/testharness.h"--namespace leveldb {--class FileNameTest { };--TEST(FileNameTest, Parse) {-  Slice db;-  FileType type;-  uint64_t number;--  // Successful parses-  static struct {-    const char* fname;-    uint64_t number;-    FileType type;-  } cases[] = {-    { "100.log",            100,   kLogFile },-    { "0.log",              0,     kLogFile },-    { "0.sst",              0,     kTableFile },-    { "CURRENT",            0,     kCurrentFile },-    { "LOCK",               0,     kDBLockFile },-    { "MANIFEST-2",         2,     kDescriptorFile },-    { "MANIFEST-7",         7,     kDescriptorFile },-    { "LOG",                0,     kInfoLogFile },-    { "LOG.old",            0,     kInfoLogFile },-    { "18446744073709551615.log", 18446744073709551615ull, kLogFile },-  };-  for (int i = 0; i < sizeof(cases) / sizeof(cases[0]); i++) {-    std::string f = cases[i].fname;-    ASSERT_TRUE(ParseFileName(f, &number, &type)) << f;-    ASSERT_EQ(cases[i].type, type) << f;-    ASSERT_EQ(cases[i].number, number) << f;-  }--  // Errors-  static const char* errors[] = {-    "",-    "foo",-    "foo-dx-100.log",-    ".log",-    "",-    "manifest",-    "CURREN",-    "CURRENTX",-    "MANIFES",-    "MANIFEST",-    "MANIFEST-",-    "XMANIFEST-3",-    "MANIFEST-3x",-    "LOC",-    "LOCKx",-    "LO",-    "LOGx",-    "18446744073709551616.log",-    "184467440737095516150.log",-    "100",-    "100.",-    "100.lop"-  };-  for (int i = 0; i < sizeof(errors) / sizeof(errors[0]); i++) {-    std::string f = errors[i];-    ASSERT_TRUE(!ParseFileName(f, &number, &type)) << f;-  };-}--TEST(FileNameTest, Construction) {-  uint64_t number;-  FileType type;-  std::string fname;--  fname = CurrentFileName("foo");-  ASSERT_EQ("foo/", std::string(fname.data(), 4));-  ASSERT_TRUE(ParseFileName(fname.c_str() + 4, &number, &type));-  ASSERT_EQ(0, number);-  ASSERT_EQ(kCurrentFile, type);--  fname = LockFileName("foo");-  ASSERT_EQ("foo/", std::string(fname.data(), 4));-  ASSERT_TRUE(ParseFileName(fname.c_str() + 4, &number, &type));-  ASSERT_EQ(0, number);-  ASSERT_EQ(kDBLockFile, type);--  fname = LogFileName("foo", 192);-  ASSERT_EQ("foo/", std::string(fname.data(), 4));-  ASSERT_TRUE(ParseFileName(fname.c_str() + 4, &number, &type));-  ASSERT_EQ(192, number);-  ASSERT_EQ(kLogFile, type);--  fname = TableFileName("bar", 200);-  ASSERT_EQ("bar/", std::string(fname.data(), 4));-  ASSERT_TRUE(ParseFileName(fname.c_str() + 4, &number, &type));-  ASSERT_EQ(200, number);-  ASSERT_EQ(kTableFile, type);--  fname = DescriptorFileName("bar", 100);-  ASSERT_EQ("bar/", std::string(fname.data(), 4));-  ASSERT_TRUE(ParseFileName(fname.c_str() + 4, &number, &type));-  ASSERT_EQ(100, number);-  ASSERT_EQ(kDescriptorFile, type);--  fname = TempFileName("tmp", 999);-  ASSERT_EQ("tmp/", std::string(fname.data(), 4));-  ASSERT_TRUE(ParseFileName(fname.c_str() + 4, &number, &type));-  ASSERT_EQ(999, number);-  ASSERT_EQ(kTempFile, type);-}--}  // namespace leveldb--int main(int argc, char** argv) {-  return leveldb::test::RunAllTests();-}

@@ -1,35 +0,0 @@-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.-// Use of this source code is governed by a BSD-style license that can be-// found in the LICENSE file. See the AUTHORS file for names of contributors.-//-// Log format information shared by reader and writer.-// See ../doc/log_format.txt for more detail.--#ifndef STORAGE_LEVELDB_DB_LOG_FORMAT_H_-#define STORAGE_LEVELDB_DB_LOG_FORMAT_H_--namespace leveldb {-namespace log {--enum RecordType {-  // Zero is reserved for preallocated files-  kZeroType = 0,--  kFullType = 1,--  // For fragments-  kFirstType = 2,-  kMiddleType = 3,-  kLastType = 4-};-static const int kMaxRecordType = kLastType;--static const int kBlockSize = 32768;--// Header is checksum (4 bytes), type (1 byte), length (2 bytes).-static const int kHeaderSize = 4 + 1 + 2;--}  // namespace log-}  // namespace leveldb--#endif  // STORAGE_LEVELDB_DB_LOG_FORMAT_H_

@@ -1,259 +0,0 @@-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.-// Use of this source code is governed by a BSD-style license that can be-// found in the LICENSE file. See the AUTHORS file for names of contributors.--#include "db/log_reader.h"--#include <stdio.h>-#include "leveldb/env.h"-#include "util/coding.h"-#include "util/crc32c.h"--namespace leveldb {-namespace log {--Reader::Reporter::~Reporter() {-}--Reader::Reader(SequentialFile* file, Reporter* reporter, bool checksum,-               uint64_t initial_offset)-    : file_(file),-      reporter_(reporter),-      checksum_(checksum),-      backing_store_(new char[kBlockSize]),-      buffer_(),-      eof_(false),-      last_record_offset_(0),-      end_of_buffer_offset_(0),-      initial_offset_(initial_offset) {-}--Reader::~Reader() {-  delete[] backing_store_;-}--bool Reader::SkipToInitialBlock() {-  size_t offset_in_block = initial_offset_ % kBlockSize;-  uint64_t block_start_location = initial_offset_ - offset_in_block;--  // Don't search a block if we'd be in the trailer-  if (offset_in_block > kBlockSize - 6) {-    offset_in_block = 0;-    block_start_location += kBlockSize;-  }--  end_of_buffer_offset_ = block_start_location;--  // Skip to start of first block that can contain the initial record-  if (block_start_location > 0) {-    Status skip_status = file_->Skip(block_start_location);-    if (!skip_status.ok()) {-      ReportDrop(block_start_location, skip_status);-      return false;-    }-  }--  return true;-}--bool Reader::ReadRecord(Slice* record, std::string* scratch) {-  if (last_record_offset_ < initial_offset_) {-    if (!SkipToInitialBlock()) {-      return false;-    }-  }--  scratch->clear();-  record->clear();-  bool in_fragmented_record = false;-  // Record offset of the logical record that we're reading-  // 0 is a dummy value to make compilers happy-  uint64_t prospective_record_offset = 0;--  Slice fragment;-  while (true) {-    uint64_t physical_record_offset = end_of_buffer_offset_ - buffer_.size();-    const unsigned int record_type = ReadPhysicalRecord(&fragment);-    switch (record_type) {-      case kFullType:-        if (in_fragmented_record) {-          // Handle bug in earlier versions of log::Writer where-          // it could emit an empty kFirstType record at the tail end-          // of a block followed by a kFullType or kFirstType record-          // at the beginning of the next block.-          if (scratch->empty()) {-            in_fragmented_record = false;-          } else {-            ReportCorruption(scratch->size(), "partial record without end(1)");-          }-        }-        prospective_record_offset = physical_record_offset;-        scratch->clear();-        *record = fragment;-        last_record_offset_ = prospective_record_offset;-        return true;--      case kFirstType:-        if (in_fragmented_record) {-          // Handle bug in earlier versions of log::Writer where-          // it could emit an empty kFirstType record at the tail end-          // of a block followed by a kFullType or kFirstType record-          // at the beginning of the next block.-          if (scratch->empty()) {-            in_fragmented_record = false;-          } else {-            ReportCorruption(scratch->size(), "partial record without end(2)");-          }-        }-        prospective_record_offset = physical_record_offset;-        scratch->assign(fragment.data(), fragment.size());-        in_fragmented_record = true;-        break;--      case kMiddleType:-        if (!in_fragmented_record) {-          ReportCorruption(fragment.size(),-                           "missing start of fragmented record(1)");-        } else {-          scratch->append(fragment.data(), fragment.size());-        }-        break;--      case kLastType:-        if (!in_fragmented_record) {-          ReportCorruption(fragment.size(),-                           "missing start of fragmented record(2)");-        } else {-          scratch->append(fragment.data(), fragment.size());-          *record = Slice(*scratch);-          last_record_offset_ = prospective_record_offset;-          return true;-        }-        break;--      case kEof:-        if (in_fragmented_record) {-          ReportCorruption(scratch->size(), "partial record without end(3)");-          scratch->clear();-        }-        return false;--      case kBadRecord:-        if (in_fragmented_record) {-          ReportCorruption(scratch->size(), "error in middle of record");-          in_fragmented_record = false;-          scratch->clear();-        }-        break;--      default: {-        char buf[40];-        snprintf(buf, sizeof(buf), "unknown record type %u", record_type);-        ReportCorruption(-            (fragment.size() + (in_fragmented_record ? scratch->size() : 0)),-            buf);-        in_fragmented_record = false;-        scratch->clear();-        break;-      }-    }-  }-  return false;-}--uint64_t Reader::LastRecordOffset() {-  return last_record_offset_;-}--void Reader::ReportCorruption(size_t bytes, const char* reason) {-  ReportDrop(bytes, Status::Corruption(reason));-}--void Reader::ReportDrop(size_t bytes, const Status& reason) {-  if (reporter_ != NULL &&-      end_of_buffer_offset_ - buffer_.size() - bytes >= initial_offset_) {-    reporter_->Corruption(bytes, reason);-  }-}--unsigned int Reader::ReadPhysicalRecord(Slice* result) {-  while (true) {-    if (buffer_.size() < kHeaderSize) {-      if (!eof_) {-        // Last read was a full read, so this is a trailer to skip-        buffer_.clear();-        Status status = file_->Read(kBlockSize, &buffer_, backing_store_);-        end_of_buffer_offset_ += buffer_.size();-        if (!status.ok()) {-          buffer_.clear();-          ReportDrop(kBlockSize, status);-          eof_ = true;-          return kEof;-        } else if (buffer_.size() < kBlockSize) {-          eof_ = true;-        }-        continue;-      } else if (buffer_.size() == 0) {-        // End of file-        return kEof;-      } else {-        size_t drop_size = buffer_.size();-        buffer_.clear();-        ReportCorruption(drop_size, "truncated record at end of file");-        return kEof;-      }-    }--    // Parse the header-    const char* header = buffer_.data();-    const uint32_t a = static_cast<uint32_t>(header[4]) & 0xff;-    const uint32_t b = static_cast<uint32_t>(header[5]) & 0xff;-    const unsigned int type = header[6];-    const uint32_t length = a | (b << 8);-    if (kHeaderSize + length > buffer_.size()) {-      size_t drop_size = buffer_.size();-      buffer_.clear();-      ReportCorruption(drop_size, "bad record length");-      return kBadRecord;-    }--    if (type == kZeroType && length == 0) {-      // Skip zero length record without reporting any drops since-      // such records are produced by the mmap based writing code in-      // env_posix.cc that preallocates file regions.-      buffer_.clear();-      return kBadRecord;-    }--    // Check crc-    if (checksum_) {-      uint32_t expected_crc = crc32c::Unmask(DecodeFixed32(header));-      uint32_t actual_crc = crc32c::Value(header + 6, 1 + length);-      if (actual_crc != expected_crc) {-        // Drop the rest of the buffer since "length" itself may have-        // been corrupted and if we trust it, we could find some-        // fragment of a real log record that just happens to look-        // like a valid log record.-        size_t drop_size = buffer_.size();-        buffer_.clear();-        ReportCorruption(drop_size, "checksum mismatch");-        return kBadRecord;-      }-    }--    buffer_.remove_prefix(kHeaderSize + length);--    // Skip physical record that started before initial_offset_-    if (end_of_buffer_offset_ - buffer_.size() - kHeaderSize - length <-        initial_offset_) {-      result->clear();-      return kBadRecord;-    }--    *result = Slice(header + kHeaderSize, length);-    return type;-  }-}--}  // namespace log-}  // namespace leveldb

@@ -1,108 +0,0 @@-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.-// Use of this source code is governed by a BSD-style license that can be-// found in the LICENSE file. See the AUTHORS file for names of contributors.--#ifndef STORAGE_LEVELDB_DB_LOG_READER_H_-#define STORAGE_LEVELDB_DB_LOG_READER_H_--#include <stdint.h>--#include "db/log_format.h"-#include "leveldb/slice.h"-#include "leveldb/status.h"--namespace leveldb {--class SequentialFile;--namespace log {--class Reader {- public:-  // Interface for reporting errors.-  class Reporter {-   public:-    virtual ~Reporter();--    // Some corruption was detected.  "size" is the approximate number-    // of bytes dropped due to the corruption.-    virtual void Corruption(size_t bytes, const Status& status) = 0;-  };--  // Create a reader that will return log records from "*file".-  // "*file" must remain live while this Reader is in use.-  //-  // If "reporter" is non-NULL, it is notified whenever some data is-  // dropped due to a detected corruption.  "*reporter" must remain-  // live while this Reader is in use.-  //-  // If "checksum" is true, verify checksums if available.-  //-  // The Reader will start reading at the first record located at physical-  // position >= initial_offset within the file.-  Reader(SequentialFile* file, Reporter* reporter, bool checksum,-         uint64_t initial_offset);--  ~Reader();--  // Read the next record into *record.  Returns true if read-  // successfully, false if we hit end of the input.  May use-  // "*scratch" as temporary storage.  The contents filled in *record-  // will only be valid until the next mutating operation on this-  // reader or the next mutation to *scratch.-  bool ReadRecord(Slice* record, std::string* scratch);--  // Returns the physical offset of the last record returned by ReadRecord.-  //-  // Undefined before the first call to ReadRecord.-  uint64_t LastRecordOffset();-- private:-  SequentialFile* const file_;-  Reporter* const reporter_;-  bool const checksum_;-  char* const backing_store_;-  Slice buffer_;-  bool eof_;   // Last Read() indicated EOF by returning < kBlockSize--  // Offset of the last record returned by ReadRecord.-  uint64_t last_record_offset_;-  // Offset of the first location past the end of buffer_.-  uint64_t end_of_buffer_offset_;--  // Offset at which to start looking for the first record to return-  uint64_t const initial_offset_;--  // Extend record types with the following special values-  enum {-    kEof = kMaxRecordType + 1,-    // Returned whenever we find an invalid physical record.-    // Currently there are three situations in which this happens:-    // * The record has an invalid CRC (ReadPhysicalRecord reports a drop)-    // * The record is a 0-length record (No drop is reported)-    // * The record is below constructor's initial_offset (No drop is reported)-    kBadRecord = kMaxRecordType + 2-  };--  // Skips all blocks that are completely before "initial_offset_".-  //-  // Returns true on success. Handles reporting.-  bool SkipToInitialBlock();--  // Return type, or one of the preceding special values-  unsigned int ReadPhysicalRecord(Slice* result);--  // Reports dropped bytes to the reporter.-  // buffer_ must be updated to remove the dropped bytes prior to invocation.-  void ReportCorruption(size_t bytes, const char* reason);-  void ReportDrop(size_t bytes, const Status& reason);--  // No copying allowed-  Reader(const Reader&);-  void operator=(const Reader&);-};--}  // namespace log-}  // namespace leveldb--#endif  // STORAGE_LEVELDB_DB_LOG_READER_H_

@@ -1,500 +0,0 @@-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.-// Use of this source code is governed by a BSD-style license that can be-// found in the LICENSE file. See the AUTHORS file for names of contributors.--#include "db/log_reader.h"-#include "db/log_writer.h"-#include "leveldb/env.h"-#include "util/coding.h"-#include "util/crc32c.h"-#include "util/random.h"-#include "util/testharness.h"--namespace leveldb {-namespace log {--// Construct a string of the specified length made out of the supplied-// partial string.-static std::string BigString(const std::string& partial_string, size_t n) {-  std::string result;-  while (result.size() < n) {-    result.append(partial_string);-  }-  result.resize(n);-  return result;-}--// Construct a string from a number-static std::string NumberString(int n) {-  char buf[50];-  snprintf(buf, sizeof(buf), "%d.", n);-  return std::string(buf);-}--// Return a skewed potentially long string-static std::string RandomSkewedString(int i, Random* rnd) {-  return BigString(NumberString(i), rnd->Skewed(17));-}--class LogTest {- private:-  class StringDest : public WritableFile {-   public:-    std::string contents_;--    virtual Status Close() { return Status::OK(); }-    virtual Status Flush() { return Status::OK(); }-    virtual Status Sync() { return Status::OK(); }-    virtual Status Append(const Slice& slice) {-      contents_.append(slice.data(), slice.size());-      return Status::OK();-    }-  };--  class StringSource : public SequentialFile {-   public:-    Slice contents_;-    bool force_error_;-    bool returned_partial_;-    StringSource() : force_error_(false), returned_partial_(false) { }--    virtual Status Read(size_t n, Slice* result, char* scratch) {-      ASSERT_TRUE(!returned_partial_) << "must not Read() after eof/error";--      if (force_error_) {-        force_error_ = false;-        returned_partial_ = true;-        return Status::Corruption("read error");-      }--      if (contents_.size() < n) {-        n = contents_.size();-        returned_partial_ = true;-      }-      *result = Slice(contents_.data(), n);-      contents_.remove_prefix(n);-      return Status::OK();-    }--    virtual Status Skip(uint64_t n) {-      if (n > contents_.size()) {-        contents_.clear();-        return Status::NotFound("in-memory file skipepd past end");-      }--      contents_.remove_prefix(n);--      return Status::OK();-    }-  };--  class ReportCollector : public Reader::Reporter {-   public:-    size_t dropped_bytes_;-    std::string message_;--    ReportCollector() : dropped_bytes_(0) { }-    virtual void Corruption(size_t bytes, const Status& status) {-      dropped_bytes_ += bytes;-      message_.append(status.ToString());-    }-  };--  StringDest dest_;-  StringSource source_;-  ReportCollector report_;-  bool reading_;-  Writer writer_;-  Reader reader_;--  // Record metadata for testing initial offset functionality-  static size_t initial_offset_record_sizes_[];-  static uint64_t initial_offset_last_record_offsets_[];-- public:-  LogTest() : reading_(false),-              writer_(&dest_),-              reader_(&source_, &report_, true/*checksum*/,-                      0/*initial_offset*/) {-  }--  void Write(const std::string& msg) {-    ASSERT_TRUE(!reading_) << "Write() after starting to read";-    writer_.AddRecord(Slice(msg));-  }--  size_t WrittenBytes() const {-    return dest_.contents_.size();-  }--  std::string Read() {-    if (!reading_) {-      reading_ = true;-      source_.contents_ = Slice(dest_.contents_);-    }-    std::string scratch;-    Slice record;-    if (reader_.ReadRecord(&record, &scratch)) {-      return record.ToString();-    } else {-      return "EOF";-    }-  }--  void IncrementByte(int offset, int delta) {-    dest_.contents_[offset] += delta;-  }--  void SetByte(int offset, char new_byte) {-    dest_.contents_[offset] = new_byte;-  }--  void ShrinkSize(int bytes) {-    dest_.contents_.resize(dest_.contents_.size() - bytes);-  }--  void FixChecksum(int header_offset, int len) {-    // Compute crc of type/len/data-    uint32_t crc = crc32c::Value(&dest_.contents_[header_offset+6], 1 + len);-    crc = crc32c::Mask(crc);-    EncodeFixed32(&dest_.contents_[header_offset], crc);-  }--  void ForceError() {-    source_.force_error_ = true;-  }--  size_t DroppedBytes() const {-    return report_.dropped_bytes_;-  }--  std::string ReportMessage() const {-    return report_.message_;-  }--  // Returns OK iff recorded error message contains "msg"-  std::string MatchError(const std::string& msg) const {-    if (report_.message_.find(msg) == std::string::npos) {-      return report_.message_;-    } else {-      return "OK";-    }-  }--  void WriteInitialOffsetLog() {-    for (int i = 0; i < 4; i++) {-      std::string record(initial_offset_record_sizes_[i],-                         static_cast<char>('a' + i));-      Write(record);-    }-  }--  void CheckOffsetPastEndReturnsNoRecords(uint64_t offset_past_end) {-    WriteInitialOffsetLog();-    reading_ = true;-    source_.contents_ = Slice(dest_.contents_);-    Reader* offset_reader = new Reader(&source_, &report_, true/*checksum*/,-                                       WrittenBytes() + offset_past_end);-    Slice record;-    std::string scratch;-    ASSERT_TRUE(!offset_reader->ReadRecord(&record, &scratch));-    delete offset_reader;-  }--  void CheckInitialOffsetRecord(uint64_t initial_offset,-                                int expected_record_offset) {-    WriteInitialOffsetLog();-    reading_ = true;-    source_.contents_ = Slice(dest_.contents_);-    Reader* offset_reader = new Reader(&source_, &report_, true/*checksum*/,-                                       initial_offset);-    Slice record;-    std::string scratch;-    ASSERT_TRUE(offset_reader->ReadRecord(&record, &scratch));-    ASSERT_EQ(initial_offset_record_sizes_[expected_record_offset],-              record.size());-    ASSERT_EQ(initial_offset_last_record_offsets_[expected_record_offset],-              offset_reader->LastRecordOffset());-    ASSERT_EQ((char)('a' + expected_record_offset), record.data()[0]);-    delete offset_reader;-  }--};--size_t LogTest::initial_offset_record_sizes_[] =-    {10000,  // Two sizable records in first block-     10000,-     2 * log::kBlockSize - 1000,  // Span three blocks-     1};--uint64_t LogTest::initial_offset_last_record_offsets_[] =-    {0,-     kHeaderSize + 10000,-     2 * (kHeaderSize + 10000),-     2 * (kHeaderSize + 10000) +-         (2 * log::kBlockSize - 1000) + 3 * kHeaderSize};---TEST(LogTest, Empty) {-  ASSERT_EQ("EOF", Read());-}--TEST(LogTest, ReadWrite) {-  Write("foo");-  Write("bar");-  Write("");-  Write("xxxx");-  ASSERT_EQ("foo", Read());-  ASSERT_EQ("bar", Read());-  ASSERT_EQ("", Read());-  ASSERT_EQ("xxxx", Read());-  ASSERT_EQ("EOF", Read());-  ASSERT_EQ("EOF", Read());  // Make sure reads at eof work-}--TEST(LogTest, ManyBlocks) {-  for (int i = 0; i < 100000; i++) {-    Write(NumberString(i));-  }-  for (int i = 0; i < 100000; i++) {-    ASSERT_EQ(NumberString(i), Read());-  }-  ASSERT_EQ("EOF", Read());-}--TEST(LogTest, Fragmentation) {-  Write("small");-  Write(BigString("medium", 50000));-  Write(BigString("large", 100000));-  ASSERT_EQ("small", Read());-  ASSERT_EQ(BigString("medium", 50000), Read());-  ASSERT_EQ(BigString("large", 100000), Read());-  ASSERT_EQ("EOF", Read());-}--TEST(LogTest, MarginalTrailer) {-  // Make a trailer that is exactly the same length as an empty record.-  const int n = kBlockSize - 2*kHeaderSize;-  Write(BigString("foo", n));-  ASSERT_EQ(kBlockSize - kHeaderSize, WrittenBytes());-  Write("");-  Write("bar");-  ASSERT_EQ(BigString("foo", n), Read());-  ASSERT_EQ("", Read());-  ASSERT_EQ("bar", Read());-  ASSERT_EQ("EOF", Read());-}--TEST(LogTest, MarginalTrailer2) {-  // Make a trailer that is exactly the same length as an empty record.-  const int n = kBlockSize - 2*kHeaderSize;-  Write(BigString("foo", n));-  ASSERT_EQ(kBlockSize - kHeaderSize, WrittenBytes());-  Write("bar");-  ASSERT_EQ(BigString("foo", n), Read());-  ASSERT_EQ("bar", Read());-  ASSERT_EQ("EOF", Read());-  ASSERT_EQ(0, DroppedBytes());-  ASSERT_EQ("", ReportMessage());-}--TEST(LogTest, ShortTrailer) {-  const int n = kBlockSize - 2*kHeaderSize + 4;-  Write(BigString("foo", n));-  ASSERT_EQ(kBlockSize - kHeaderSize + 4, WrittenBytes());-  Write("");-  Write("bar");-  ASSERT_EQ(BigString("foo", n), Read());-  ASSERT_EQ("", Read());-  ASSERT_EQ("bar", Read());-  ASSERT_EQ("EOF", Read());-}--TEST(LogTest, AlignedEof) {-  const int n = kBlockSize - 2*kHeaderSize + 4;-  Write(BigString("foo", n));-  ASSERT_EQ(kBlockSize - kHeaderSize + 4, WrittenBytes());-  ASSERT_EQ(BigString("foo", n), Read());-  ASSERT_EQ("EOF", Read());-}--TEST(LogTest, RandomRead) {-  const int N = 500;-  Random write_rnd(301);-  for (int i = 0; i < N; i++) {-    Write(RandomSkewedString(i, &write_rnd));-  }-  Random read_rnd(301);-  for (int i = 0; i < N; i++) {-    ASSERT_EQ(RandomSkewedString(i, &read_rnd), Read());-  }-  ASSERT_EQ("EOF", Read());-}--// Tests of all the error paths in log_reader.cc follow:--TEST(LogTest, ReadError) {-  Write("foo");-  ForceError();-  ASSERT_EQ("EOF", Read());-  ASSERT_EQ(kBlockSize, DroppedBytes());-  ASSERT_EQ("OK", MatchError("read error"));-}--TEST(LogTest, BadRecordType) {-  Write("foo");-  // Type is stored in header[6]-  IncrementByte(6, 100);-  FixChecksum(0, 3);-  ASSERT_EQ("EOF", Read());-  ASSERT_EQ(3, DroppedBytes());-  ASSERT_EQ("OK", MatchError("unknown record type"));-}--TEST(LogTest, TruncatedTrailingRecord) {-  Write("foo");-  ShrinkSize(4);   // Drop all payload as well as a header byte-  ASSERT_EQ("EOF", Read());-  ASSERT_EQ(kHeaderSize - 1, DroppedBytes());-  ASSERT_EQ("OK", MatchError("truncated record at end of file"));-}--TEST(LogTest, BadLength) {-  Write("foo");-  ShrinkSize(1);-  ASSERT_EQ("EOF", Read());-  ASSERT_EQ(kHeaderSize + 2, DroppedBytes());-  ASSERT_EQ("OK", MatchError("bad record length"));-}--TEST(LogTest, ChecksumMismatch) {-  Write("foo");-  IncrementByte(0, 10);-  ASSERT_EQ("EOF", Read());-  ASSERT_EQ(10, DroppedBytes());-  ASSERT_EQ("OK", MatchError("checksum mismatch"));-}--TEST(LogTest, UnexpectedMiddleType) {-  Write("foo");-  SetByte(6, kMiddleType);-  FixChecksum(0, 3);-  ASSERT_EQ("EOF", Read());-  ASSERT_EQ(3, DroppedBytes());-  ASSERT_EQ("OK", MatchError("missing start"));-}--TEST(LogTest, UnexpectedLastType) {-  Write("foo");-  SetByte(6, kLastType);-  FixChecksum(0, 3);-  ASSERT_EQ("EOF", Read());-  ASSERT_EQ(3, DroppedBytes());-  ASSERT_EQ("OK", MatchError("missing start"));-}--TEST(LogTest, UnexpectedFullType) {-  Write("foo");-  Write("bar");-  SetByte(6, kFirstType);-  FixChecksum(0, 3);-  ASSERT_EQ("bar", Read());-  ASSERT_EQ("EOF", Read());-  ASSERT_EQ(3, DroppedBytes());-  ASSERT_EQ("OK", MatchError("partial record without end"));-}--TEST(LogTest, UnexpectedFirstType) {-  Write("foo");-  Write(BigString("bar", 100000));-  SetByte(6, kFirstType);-  FixChecksum(0, 3);-  ASSERT_EQ(BigString("bar", 100000), Read());-  ASSERT_EQ("EOF", Read());-  ASSERT_EQ(3, DroppedBytes());-  ASSERT_EQ("OK", MatchError("partial record without end"));-}--TEST(LogTest, ErrorJoinsRecords) {-  // Consider two fragmented records:-  //    first(R1) last(R1) first(R2) last(R2)-  // where the middle two fragments disappear.  We do not want-  // first(R1),last(R2) to get joined and returned as a valid record.--  // Write records that span two blocks-  Write(BigString("foo", kBlockSize));-  Write(BigString("bar", kBlockSize));-  Write("correct");--  // Wipe the middle block-  for (int offset = kBlockSize; offset < 2*kBlockSize; offset++) {-    SetByte(offset, 'x');-  }--  ASSERT_EQ("correct", Read());-  ASSERT_EQ("EOF", Read());-  const int dropped = DroppedBytes();-  ASSERT_LE(dropped, 2*kBlockSize + 100);-  ASSERT_GE(dropped, 2*kBlockSize);-}--TEST(LogTest, ReadStart) {-  CheckInitialOffsetRecord(0, 0);-}--TEST(LogTest, ReadSecondOneOff) {-  CheckInitialOffsetRecord(1, 1);-}--TEST(LogTest, ReadSecondTenThousand) {-  CheckInitialOffsetRecord(10000, 1);-}--TEST(LogTest, ReadSecondStart) {-  CheckInitialOffsetRecord(10007, 1);-}--TEST(LogTest, ReadThirdOneOff) {-  CheckInitialOffsetRecord(10008, 2);-}--TEST(LogTest, ReadThirdStart) {-  CheckInitialOffsetRecord(20014, 2);-}--TEST(LogTest, ReadFourthOneOff) {-  CheckInitialOffsetRecord(20015, 3);-}--TEST(LogTest, ReadFourthFirstBlockTrailer) {-  CheckInitialOffsetRecord(log::kBlockSize - 4, 3);-}--TEST(LogTest, ReadFourthMiddleBlock) {-  CheckInitialOffsetRecord(log::kBlockSize + 1, 3);-}--TEST(LogTest, ReadFourthLastBlock) {-  CheckInitialOffsetRecord(2 * log::kBlockSize + 1, 3);-}--TEST(LogTest, ReadFourthStart) {-  CheckInitialOffsetRecord(-      2 * (kHeaderSize + 1000) + (2 * log::kBlockSize - 1000) + 3 * kHeaderSize,-      3);-}--TEST(LogTest, ReadEnd) {-  CheckOffsetPastEndReturnsNoRecords(0);-}--TEST(LogTest, ReadPastEnd) {-  CheckOffsetPastEndReturnsNoRecords(5);-}--}  // namespace log-}  // namespace leveldb--int main(int argc, char** argv) {-  return leveldb::test::RunAllTests();-}

@@ -1,103 +0,0 @@-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.-// Use of this source code is governed by a BSD-style license that can be-// found in the LICENSE file. See the AUTHORS file for names of contributors.--#include "db/log_writer.h"--#include <stdint.h>-#include "leveldb/env.h"-#include "util/coding.h"-#include "util/crc32c.h"--namespace leveldb {-namespace log {--Writer::Writer(WritableFile* dest)-    : dest_(dest),-      block_offset_(0) {-  for (int i = 0; i <= kMaxRecordType; i++) {-    char t = static_cast<char>(i);-    type_crc_[i] = crc32c::Value(&t, 1);-  }-}--Writer::~Writer() {-}--Status Writer::AddRecord(const Slice& slice) {-  const char* ptr = slice.data();-  size_t left = slice.size();--  // Fragment the record if necessary and emit it.  Note that if slice-  // is empty, we still want to iterate once to emit a single-  // zero-length record-  Status s;-  bool begin = true;-  do {-    const int leftover = kBlockSize - block_offset_;-    assert(leftover >= 0);-    if (leftover < kHeaderSize) {-      // Switch to a new block-      if (leftover > 0) {-        // Fill the trailer (literal below relies on kHeaderSize being 7)-        assert(kHeaderSize == 7);-        dest_->Append(Slice("\x00\x00\x00\x00\x00\x00", leftover));-      }-      block_offset_ = 0;-    }--    // Invariant: we never leave < kHeaderSize bytes in a block.-    assert(kBlockSize - block_offset_ - kHeaderSize >= 0);--    const size_t avail = kBlockSize - block_offset_ - kHeaderSize;-    const size_t fragment_length = (left < avail) ? left : avail;--    RecordType type;-    const bool end = (left == fragment_length);-    if (begin && end) {-      type = kFullType;-    } else if (begin) {-      type = kFirstType;-    } else if (end) {-      type = kLastType;-    } else {-      type = kMiddleType;-    }--    s = EmitPhysicalRecord(type, ptr, fragment_length);-    ptr += fragment_length;-    left -= fragment_length;-    begin = false;-  } while (s.ok() && left > 0);-  return s;-}--Status Writer::EmitPhysicalRecord(RecordType t, const char* ptr, size_t n) {-  assert(n <= 0xffff);  // Must fit in two bytes-  assert(block_offset_ + kHeaderSize + n <= kBlockSize);--  // Format the header-  char buf[kHeaderSize];-  buf[4] = static_cast<char>(n & 0xff);-  buf[5] = static_cast<char>(n >> 8);-  buf[6] = static_cast<char>(t);--  // Compute the crc of the record type and the payload.-  uint32_t crc = crc32c::Extend(type_crc_[t], ptr, n);-  crc = crc32c::Mask(crc);                 // Adjust for storage-  EncodeFixed32(buf, crc);--  // Write the header and the payload-  Status s = dest_->Append(Slice(buf, kHeaderSize));-  if (s.ok()) {-    s = dest_->Append(Slice(ptr, n));-    if (s.ok()) {-      s = dest_->Flush();-    }-  }-  block_offset_ += kHeaderSize + n;-  return s;-}--}  // namespace log-}  // namespace leveldb

@@ -1,48 +0,0 @@-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.-// Use of this source code is governed by a BSD-style license that can be-// found in the LICENSE file. See the AUTHORS file for names of contributors.--#ifndef STORAGE_LEVELDB_DB_LOG_WRITER_H_-#define STORAGE_LEVELDB_DB_LOG_WRITER_H_--#include <stdint.h>-#include "db/log_format.h"-#include "leveldb/slice.h"-#include "leveldb/status.h"--namespace leveldb {--class WritableFile;--namespace log {--class Writer {- public:-  // Create a writer that will append data to "*dest".-  // "*dest" must be initially empty.-  // "*dest" must remain live while this Writer is in use.-  explicit Writer(WritableFile* dest);-  ~Writer();--  Status AddRecord(const Slice& slice);-- private:-  WritableFile* dest_;-  int block_offset_;       // Current offset in block--  // crc32c values for all supported record types.  These are-  // pre-computed to reduce the overhead of computing the crc of the-  // record type stored in the header.-  uint32_t type_crc_[kMaxRecordType + 1];--  Status EmitPhysicalRecord(RecordType type, const char* ptr, size_t length);--  // No copying allowed-  Writer(const Writer&);-  void operator=(const Writer&);-};--}  // namespace log-}  // namespace leveldb--#endif  // STORAGE_LEVELDB_DB_LOG_WRITER_H_

@@ -1,145 +0,0 @@-// Copyright (c) 2011 The LevelDB Authors. All rights reserved.-// Use of this source code is governed by a BSD-style license that can be-// found in the LICENSE file. See the AUTHORS file for names of contributors.--#include "db/memtable.h"-#include "db/dbformat.h"-#include "leveldb/comparator.h"-#include "leveldb/env.h"-#include "leveldb/iterator.h"-#include "util/coding.h"--namespace leveldb {--static Slice GetLengthPrefixedSlice(const char* data) {-  uint32_t len;-  const char* p = data;-  p = GetVarint32Ptr(p, p + 5, &len);  // +5: we assume "p" is not corrupted-  return Slice(p, len);-}--MemTable::MemTable(const InternalKeyComparator& cmp)-    : comparator_(cmp),-      refs_(0),-      table_(comparator_, &arena_) {-}--MemTable::~MemTable() {-  assert(refs_ == 0);-}--size_t MemTable::ApproximateMemoryUsage() { return arena_.MemoryUsage(); }--int MemTable::KeyComparator::operator()(const char* aptr, const char* bptr)-    const {-  // Internal keys are encoded as length-prefixed strings.-  Slice a = GetLengthPrefixedSlice(aptr);-  Slice b = GetLengthPrefixedSlice(bptr);-  return comparator.Compare(a, b);-}--// Encode a suitable internal key target for "target" and return it.-// Uses *scratch as scratch space, and the returned pointer will point-// into this scratch space.-static const char* EncodeKey(std::string* scratch, const Slice& target) {-  scratch->clear();-  PutVarint32(scratch, target.size());-  scratch->append(target.data(), target.size());-  return scratch->data();-}--class MemTableIterator: public Iterator {- public:-  explicit MemTableIterator(MemTable::Table* table) : iter_(table) { }--  virtual bool Valid() const { return iter_.Valid(); }-  virtual void Seek(const Slice& k) { iter_.Seek(EncodeKey(&tmp_, k)); }-  virtual void SeekToFirst() { iter_.SeekToFirst(); }-  virtual void SeekToLast() { iter_.SeekToLast(); }-  virtual void Next() { iter_.Next(); }-  virtual void Prev() { iter_.Prev(); }-  virtual Slice key() const { return GetLengthPrefixedSlice(iter_.key()); }-  virtual Slice value() const {-    Slice key_slice = GetLengthPrefixedSlice(iter_.key());-    return GetLengthPrefixedSlice(key_slice.data() + key_slice.size());-  }--  virtual Status status() const { return Status::OK(); }-- private:-  MemTable::Table::Iterator iter_;-  std::string tmp_;       // For passing to EncodeKey--  // No copying allowed-  MemTableIterator(const MemTableIterator&);-  void operator=(const MemTableIterator&);-};--Iterator* MemTable::NewIterator() {-  return new MemTableIterator(&table_);-}--void MemTable::Add(SequenceNumber s, ValueType type,-                   const Slice& key,-                   const Slice& value) {-  // Format of an entry is concatenation of:-  //  key_size     : varint32 of internal_key.size()-  //  key bytes    : char[internal_key.size()]-  //  value_size   : varint32 of value.size()-  //  value bytes  : char[value.size()]-  size_t key_size = key.size();-  size_t val_size = value.size();-  size_t internal_key_size = key_size + 8;-  const size_t encoded_len =-      VarintLength(internal_key_size) + internal_key_size +-      VarintLength(val_size) + val_size;-  char* buf = arena_.Allocate(encoded_len);-  char* p = EncodeVarint32(buf, internal_key_size);-  memcpy(p, key.data(), key_size);-  p += key_size;-  EncodeFixed64(p, (s << 8) | type);-  p += 8;-  p = EncodeVarint32(p, val_size);-  memcpy(p, value.data(), val_size);-  assert((p + val_size) - buf == encoded_len);-  table_.Insert(buf);-}--bool MemTable::Get(const LookupKey& key, std::string* value, Status* s) {-  Slice memkey = key.memtable_key();-  Table::Iterator iter(&table_);-  iter.Seek(memkey.data());-  if (iter.Valid()) {-    // entry format is:-    //    klength  varint32-    //    userkey  char[klength]-    //    tag      uint64-    //    vlength  varint32-    //    value    char[vlength]-    // Check that it belongs to same user key.  We do not check the-    // sequence number since the Seek() call above should have skipped-    // all entries with overly large sequence numbers.-    const char* entry = iter.key();-    uint32_t key_length;-    const char* key_ptr = GetVarint32Ptr(entry, entry+5, &key_length);-    if (comparator_.comparator.user_comparator()->Compare(-            Slice(key_ptr, key_length - 8),-            key.user_key()) == 0) {-      // Correct user key-      const uint64_t tag = DecodeFixed64(key_ptr + key_length - 8);-      switch (static_cast<ValueType>(tag & 0xff)) {-        case kTypeValue: {-          Slice v = GetLengthPrefixedSlice(key_ptr + key_length);-          value->assign(v.data(), v.size());-          return true;-        }-        case kTypeDeletion:-          *s = Status::NotFound(Slice());-          return true;-      }-    }-  }-  return false;-}--}  // namespace leveldb