text: // 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/version_set.h"
  
  #include <stdio.h>
  
  #include <algorithm>
  
  #include "db/filename.h"
  #include "db/log_reader.h"
  #include "db/log_writer.h"
  #include "db/memtable.h"
  #include "db/table_cache.h"
  #include "leveldb/env.h"
  #include "leveldb/table_builder.h"
  #include "table/merger.h"
  #include "table/two_level_iterator.h"
  #include "util/coding.h"
  #include "util/logging.h"
  
  namespace leveldb {
  
  static size_t TargetFileSize(const Options* options) {
    return options->max_file_size;
  }
  
  // Maximum bytes of overlaps in grandparent (i.e., level+2) before we
  // stop building a single file in a level->level+1 compaction.
  static int64_t MaxGrandParentOverlapBytes(const Options* options) {
    return 10 * TargetFileSize(options);
  }
  
  // Maximum number of bytes in all compacted files.  We avoid expanding
  // the lower level file set of a compaction if it would make the
  // total compaction cover more than this many bytes.
  static int64_t ExpandedCompactionByteSizeLimit(const Options* options) {
    return 25 * TargetFileSize(options);
  }
  
  static double MaxBytesForLevel(const Options* options, int level) {
    // Note: the result for level zero is not really used since we set
    // the level-0 compaction threshold based on number of files.
  
    // Result for both level-0 and level-1
    double result = 10. * 1048576.0;
    while (level > 1) {
      result *= 10;
      level--;
    }
    return result;
  }
  
  static uint64_t MaxFileSizeForLevel(const Options* options, int level) {
    // We could vary per level to reduce number of files?
    return TargetFileSize(options);
  }
  
  static int64_t TotalFileSize(const std::vector<FileMetaData*>& files) {
    int64_t sum = 0;
    for (size_t i = 0; i < files.size(); i++) {
      sum += files[i]->file_size;
    }
    return sum;
  }
  
  Version::~Version() {
    assert(refs_ == 0);
  
    // Remove from linked list
    prev_->next_ = next_;
    next_->prev_ = prev_;
  
    // Drop references to files
    for (int level = 0; level < config::kNumLevels; level++) {
      for (size_t i = 0; i < files_[level].size(); i++) {
        FileMetaData* f = files_[level][i];
        assert(f->refs > 0);
        f->refs--;
        if (f->refs <= 0) {
          delete f;
        }
      }
    }
  }
  
  int FindFile(const InternalKeyComparator& icmp,
               const std::vector<FileMetaData*>& files, const Slice& key) {
    uint32_t left = 0;
    uint32_t right = files.size();
    while (left < right) {
      uint32_t mid = (left + right) / 2;
      const FileMetaData* f = files[mid];
      if (icmp.InternalKeyComparator::Compare(f->largest.Encode(), key) < 0) {
        // Key at "mid.largest" is < "target".  Therefore all
        // files at or before "mid" are uninteresting.
        left = mid + 1;
      } else {
        // Key at "mid.largest" is >= "target".  Therefore all files
        // after "mid" are uninteresting.
        right = mid;
      }
    }
    return right;
  }
  
  static bool AfterFile(const Comparator* ucmp, const Slice* user_key,
                        const FileMetaData* f) {
    // null user_key occurs before all keys and is therefore never after *f
    return (user_key != nullptr &&
            ucmp->Compare(*user_key, f->largest.user_key()) > 0);
  }
  
  static bool BeforeFile(const Comparator* ucmp, const Slice* user_key,
                         const FileMetaData* f) {
    // null user_key occurs after all keys and is therefore never before *f
    return (user_key != nullptr &&
            ucmp->Compare(*user_key, f->smallest.user_key()) < 0);
  }
  
  bool SomeFileOverlapsRange(const InternalKeyComparator& icmp,
                             bool disjoint_sorted_files,
                             const std::vector<FileMetaData*>& files,
                             const Slice* smallest_user_key,
                             const Slice* largest_user_key) {
    const Comparator* ucmp = icmp.user_comparator();
    if (!disjoint_sorted_files) {
      // Need to check against all files
      for (size_t i = 0; i < files.size(); i++) {
        const FileMetaData* f = files[i];
        if (AfterFile(ucmp, smallest_user_key, f) ||
            BeforeFile(ucmp, largest_user_key, f)) {
          // No overlap
        } else {
          return true;  // Overlap
        }
      }
      return false;
    }
  
    // Binary search over file list
    uint32_t index = 0;
    if (smallest_user_key != nullptr) {
      // Find the earliest possible internal key for smallest_user_key
      InternalKey small_key(*smallest_user_key, kMaxSequenceNumber,
                            kValueTypeForSeek);
      index = FindFile(icmp, files, small_key.Encode());
    }
  
    if (index >= files.size()) {
      // beginning of range is after all files, so no overlap.
      return false;
    }
  
    return !BeforeFile(ucmp, largest_user_key, files[index]);
  }
  
  // An internal iterator.  For a given version/level pair, yields
  // information about the files in the level.  For a given entry, key()
  // is the largest key that occurs in the file, and value() is an
  // 16-byte value containing the file number and file size, both
  // encoded using EncodeFixed64.
  class Version::LevelFileNumIterator : public Iterator {
   public:
    LevelFileNumIterator(const InternalKeyComparator& icmp,
                         const std::vector<FileMetaData*>* flist)
        : icmp_(icmp), flist_(flist), index_(flist->size()) {  // Marks as invalid
    }
    bool Valid() const override { return index_ < flist_->size(); }
    void Seek(const Slice& target) override {
      index_ = FindFile(icmp_, *flist_, target);
    }
    void SeekToFirst() override { index_ = 0; }
    void SeekToLast() override {
      index_ = flist_->empty() ? 0 : flist_->size() - 1;
    }
    void Next() override {
      assert(Valid());
      index_++;
    }
    void Prev() override {
      assert(Valid());
      if (index_ == 0) {
        index_ = flist_->size();  // Marks as invalid
      } else {
        index_--;
      }
    }
    Slice key() const override {
      assert(Valid());
      return (*flist_)[index_]->largest.Encode();
    }
    Slice value() const override {
      assert(Valid());
      EncodeFixed64(value_buf_, (*flist_)[index_]->number);
      EncodeFixed64(value_buf_ + 8, (*flist_)[index_]->file_size);
      return Slice(value_buf_, sizeof(value_buf_));
    }
    Status status() const override { return Status::OK(); }
  
   private:
    const InternalKeyComparator icmp_;
    const std::vector<FileMetaData*>* const flist_;
    uint32_t index_;
  
    // Backing store for value().  Holds the file number and size.
    mutable char value_buf_[16];
  };
  
  static Iterator* GetFileIterator(void* arg, const ReadOptions& options,
                                   const Slice& file_value) {
    TableCache* cache = reinterpret_cast<TableCache*>(arg);
    if (file_value.size() != 16) {
      return NewErrorIterator(
          Status::Corruption("FileReader invoked with unexpected value"));
    } else {
      return cache->NewIterator(options, DecodeFixed64(file_value.data()),
                                DecodeFixed64(file_value.data() + 8));
    }
  }
  
  Iterator* Version::NewConcatenatingIterator(const ReadOptions& options,
                                              int level) const {
    return NewTwoLevelIterator(
        new LevelFileNumIterator(vset_->icmp_, &files_[level]), &GetFileIterator,
        vset_->table_cache_, options);
  }
  
  void Version::AddIterators(const ReadOptions& options,
                             std::vector<Iterator*>* iters) {
    // Merge all level zero files together since they may overlap
    for (size_t i = 0; i < files_[0].size(); i++) {
      iters->push_back(vset_->table_cache_->NewIterator(
          options, files_[0][i]->number, files_[0][i]->file_size));
    }
  
    // For levels > 0, we can use a concatenating iterator that sequentially
    // walks through the non-overlapping files in the level, opening them
    // lazily.
    for (int level = 1; level < config::kNumLevels; level++) {
      if (!files_[level].empty()) {
        iters->push_back(NewConcatenatingIterator(options, level));
      }
    }
  }
  
  // Callback from TableCache::Get()
  namespace {
  enum SaverState {
    kNotFound,
    kFound,
    kDeleted,
    kCorrupt,
  };
  struct Saver {
    SaverState state;
    const Comparator* ucmp;
    Slice user_key;
    std::string* value;
  };
  }  // namespace
  static void SaveValue(void* arg, const Slice& ikey, const Slice& v) {
    Saver* s = reinterpret_cast<Saver*>(arg);
    ParsedInternalKey parsed_key;
    if (!ParseInternalKey(ikey, &parsed_key)) {
      s->state = kCorrupt;
    } else {
      if (s->ucmp->Compare(parsed_key.user_key, s->user_key) == 0) {
        s->state = (parsed_key.type == kTypeValue) ? kFound : kDeleted;
        if (s->state == kFound) {
          s->value->assign(v.data(), v.size());
        }
      }
    }
  }
  
  static bool NewestFirst(FileMetaData* a, FileMetaData* b) {
    return a->number > b->number;
  }
  
  void Version::ForEachOverlapping(Slice user_key, Slice internal_key, void* arg,
                                   bool (*func)(void*, int, FileMetaData*)) {
    const Comparator* ucmp = vset_->icmp_.user_comparator();
  
    // Search level-0 in order from newest to oldest.
    std::vector<FileMetaData*> tmp;
    tmp.reserve(files_[0].size());
    for (uint32_t i = 0; i < files_[0].size(); i++) {
      FileMetaData* f = files_[0][i];
      if (ucmp->Compare(user_key, f->smallest.user_key()) >= 0 &&
          ucmp->Compare(user_key, f->largest.user_key()) <= 0) {
        tmp.push_back(f);
      }
    }
    if (!tmp.empty()) {
      std::sort(tmp.begin(), tmp.end(), NewestFirst);
      for (uint32_t i = 0; i < tmp.size(); i++) {
        if (!(*func)(arg, 0, tmp[i])) {
          return;
        }
      }
    }
  
    // Search other levels.
    for (int level = 1; level < config::kNumLevels; level++) {
      size_t num_files = files_[level].size();
      if (num_files == 0) continue;
  
      // Binary search to find earliest index whose largest key >= internal_key.
      uint32_t index = FindFile(vset_->icmp_, files_[level], internal_key);
      if (index < num_files) {
        FileMetaData* f = files_[level][index];
        if (ucmp->Compare(user_key, f->smallest.user_key()) < 0) {
          // All of "f" is past any data for user_key
        } else {
          if (!(*func)(arg, level, f)) {
            return;
          }
        }
      }
    }
  }
  
  Status Version::Get(const ReadOptions& options, const LookupKey& k,
                      std::string* value, GetStats* stats) {
    stats->seek_file = nullptr;
    stats->seek_file_level = -1;
  
    struct State {
      Saver saver;
      GetStats* stats;
      const ReadOptions* options;
      Slice ikey;
      FileMetaData* last_file_read;
      int last_file_read_level;
  
      VersionSet* vset;
      Status s;
      bool found;
  
      static bool Match(void* arg, int level, FileMetaData* f) {
        State* state = reinterpret_cast<State*>(arg);
  
        if (state->stats->seek_file == nullptr &&
            state->last_file_read != nullptr) {
          // We have had more than one seek for this read.  Charge the 1st file.
          state->stats->seek_file = state->last_file_read;
          state->stats->seek_file_level = state->last_file_read_level;
        }
  
        state->last_file_read = f;
        state->last_file_read_level = level;
  
        state->s = state->vset->table_cache_->Get(*state->options, f->number,
                                                  f->file_size, state->ikey,
                                                  &state->saver, SaveValue);
        if (!state->s.ok()) {
          state->found = true;
          return false;
        }
        switch (state->saver.state) {
          case kNotFound:
            return true;  // Keep searching in other files
          case kFound:
            state->found = true;
            return false;
          case kDeleted:
            return false;
          case kCorrupt:
            state->s =
                Status::Corruption("corrupted key for ", state->saver.user_key);
            state->found = true;
            return false;
        }
  
        // Not reached. Added to avoid false compilation warnings of
        // "control reaches end of non-void function".
        return false;
      }
    };
  
    State state;
    state.found = false;
    state.stats = stats;
    state.last_file_read = nullptr;
    state.last_file_read_level = -1;
  
    state.options = &options;
    state.ikey = k.internal_key();
    state.vset = vset_;
  
    state.saver.state = kNotFound;
    state.saver.ucmp = vset_->icmp_.user_comparator();
    state.saver.user_key = k.user_key();
    state.saver.value = value;
  
    ForEachOverlapping(state.saver.user_key, state.ikey, &state, &State::Match);
  
    return state.found ? state.s : Status::NotFound(Slice());
  }
  
  bool Version::UpdateStats(const GetStats& stats) {
    FileMetaData* f = stats.seek_file;
    if (f != nullptr) {
      f->allowed_seeks--;
      if (f->allowed_seeks <= 0 && file_to_compact_ == nullptr) {
        file_to_compact_ = f;
        file_to_compact_level_ = stats.seek_file_level;
        return true;
      }
    }
    return false;
  }
  
  bool Version::RecordReadSample(Slice internal_key) {
    ParsedInternalKey ikey;
    if (!ParseInternalKey(internal_key, &ikey)) {
      return false;
    }
  
    struct State {
      GetStats stats;  // Holds first matching file
      int matches;
  
      static bool Match(void* arg, int level, FileMetaData* f) {
        State* state = reinterpret_cast<State*>(arg);
        state->matches++;
        if (state->matches == 1) {
          // Remember first match.
          state->stats.seek_file = f;
          state->stats.seek_file_level = level;
        }
        // We can stop iterating once we have a second match.
        return state->matches < 2;
      }
    };
  
    State state;
    state.matches = 0;
    ForEachOverlapping(ikey.user_key, internal_key, &state, &State::Match);
  
    // Must have at least two matches since we want to merge across
    // files. But what if we have a single file that contains many
    // overwrites and deletions?  Should we have another mechanism for
    // finding such files?
    if (state.matches >= 2) {
      // 1MB cost is about 1 seek (see comment in Builder::Apply).
      return UpdateStats(state.stats);
    }
    return false;
  }
  
  void Version::Ref() { ++refs_; }
  
  void Version::Unref() {
    assert(this != &vset_->dummy_versions_);
    assert(refs_ >= 1);
    --refs_;
    if (refs_ == 0) {
      delete this;
    }
  }
  
  bool Version::OverlapInLevel(int level, const Slice* smallest_user_key,
                               const Slice* largest_user_key) {
    return SomeFileOverlapsRange(vset_->icmp_, (level > 0), files_[level],
                                 smallest_user_key, largest_user_key);
  }
  
  int Version::PickLevelForMemTableOutput(const Slice& smallest_user_key,
                                          const Slice& largest_user_key) {
    int level = 0;
    if (!OverlapInLevel(0, &smallest_user_key, &largest_user_key)) {
      // Push to next level if there is no overlap in next level,
      // and the #bytes overlapping in the level after that are limited.
      InternalKey start(smallest_user_key, kMaxSequenceNumber, kValueTypeForSeek);
      InternalKey limit(largest_user_key, 0, static_cast<ValueType>(0));
      std::vector<FileMetaData*> overlaps;
      while (level < config::kMaxMemCompactLevel) {
        if (OverlapInLevel(level + 1, &smallest_user_key, &largest_user_key)) {
          break;
        }
        if (level + 2 < config::kNumLevels) {
          // Check that file does not overlap too many grandparent bytes.
          GetOverlappingInputs(level + 2, &start, &limit, &overlaps);
          const int64_t sum = TotalFileSize(overlaps);
          if (sum > MaxGrandParentOverlapBytes(vset_->options_)) {
            break;
          }
        }
        level++;
      }
    }
    return level;
  }
  
  // Store in "*inputs" all files in "level" that overlap [begin,end]
  void Version::GetOverlappingInputs(int level, const InternalKey* begin,
                                     const InternalKey* end,
                                     std::vector<FileMetaData*>* inputs) {
    assert(level >= 0);
    assert(level < config::kNumLevels);
    inputs->clear();
    Slice user_begin, user_end;
    if (begin != nullptr) {
      user_begin = begin->user_key();
    }
    if (end != nullptr) {
      user_end = end->user_key();
    }
    const Comparator* user_cmp = vset_->icmp_.user_comparator();
    for (size_t i = 0; i < files_[level].size();) {
      FileMetaData* f = files_[level][i++];
      const Slice file_start = f->smallest.user_key();
      const Slice file_limit = f->largest.user_key();
      if (begin != nullptr && user_cmp->Compare(file_limit, user_begin) < 0) {
        // "f" is completely before specified range; skip it
      } else if (end != nullptr && user_cmp->Compare(file_start, user_end) > 0) {
        // "f" is completely after specified range; skip it
      } else {
        inputs->push_back(f);
        if (level == 0) {
          // Level-0 files may overlap each other.  So check if the newly
          // added file has expanded the range.  If so, restart search.
          if (begin != nullptr && user_cmp->Compare(file_start, user_begin) < 0) {
            user_begin = file_start;
            inputs->clear();
            i = 0;
          } else if (end != nullptr &&
                     user_cmp->Compare(file_limit, user_end) > 0) {
            user_end = file_limit;
            inputs->clear();
            i = 0;
          }
        }
      }
    }
  }
  
  std::string Version::DebugString() const {
    std::string r;
    for (int level = 0; level < config::kNumLevels; level++) {
      // E.g.,
      //   --- level 1 ---
      //   17:123['a' .. 'd']
      //   20:43['e' .. 'g']
      r.append("--- level ");
      AppendNumberTo(&r, level);
      r.append(" ---\n");
      const std::vector<FileMetaData*>& files = files_[level];
      for (size_t i = 0; i < files.size(); i++) {
        r.push_back(' ');
        AppendNumberTo(&r, files[i]->number);
        r.push_back(':');
        AppendNumberTo(&r, files[i]->file_size);
        r.append("[");
        r.append(files[i]->smallest.DebugString());
        r.append(" .. ");
        r.append(files[i]->largest.DebugString());
        r.append("]\n");
      }
    }
    return r;
  }
  
  // A helper class so we can efficiently apply a whole sequence
  // of edits to a particular state without creating intermediate
  // Versions that contain full copies of the intermediate state.
  class VersionSet::Builder {
   private:
    // Helper to sort by v->files_[file_number].smallest
    struct BySmallestKey {
      const InternalKeyComparator* internal_comparator;
  
      bool operator()(FileMetaData* f1, FileMetaData* f2) const {
        int r = internal_comparator->Compare(f1->smallest, f2->smallest);
        if (r != 0) {
          return (r < 0);
        } else {
          // Break ties by file number
          return (f1->number < f2->number);
        }
      }
    };
  
    typedef std::set<FileMetaData*, BySmallestKey> FileSet;
    struct LevelState {
      std::set<uint64_t> deleted_files;
      FileSet* added_files;
    };
  
    VersionSet* vset_;
    Version* base_;
    LevelState levels_[config::kNumLevels];
  
   public:
    // Initialize a builder with the files from *base and other info from *vset
    Builder(VersionSet* vset, Version* base) : vset_(vset), base_(base) {
      base_->Ref();
      BySmallestKey cmp;
      cmp.internal_comparator = &vset_->icmp_;
      for (int level = 0; level < config::kNumLevels; level++) {
        levels_[level].added_files = new FileSet(cmp);
      }
    }
  
    ~Builder() {
      for (int level = 0; level < config::kNumLevels; level++) {
        const FileSet* added = levels_[level].added_files;
        std::vector<FileMetaData*> to_unref;
        to_unref.reserve(added->size());
        for (FileSet::const_iterator it = added->begin(); it != added->end();
             ++it) {
          to_unref.push_back(*it);
        }
        delete added;
        for (uint32_t i = 0; i < to_unref.size(); i++) {
          FileMetaData* f = to_unref[i];
          f->refs--;
          if (f->refs <= 0) {
            delete f;
          }
        }
      }
      base_->Unref();
    }
  
    // Apply all of the edits in *edit to the current state.
    void Apply(VersionEdit* edit) {
      // Update compaction pointers
      for (size_t i = 0; i < edit->compact_pointers_.size(); i++) {
        const int level = edit->compact_pointers_[i].first;
        vset_->compact_pointer_[level] =
            edit->compact_pointers_[i].second.Encode().ToString();
      }
  
      // Delete files
      for (const auto& deleted_file_set_kvp : edit->deleted_files_) {
        const int level = deleted_file_set_kvp.first;
        const uint64_t number = deleted_file_set_kvp.second;
        levels_[level].deleted_files.insert(number);
      }
  
      // Add new files
      for (size_t i = 0; i < edit->new_files_.size(); i++) {
        const int level = edit->new_files_[i].first;
        FileMetaData* f = new FileMetaData(edit->new_files_[i].second);
        f->refs = 1;
  
        // We arrange to automatically compact this file after
        // a certain number of seeks.  Let's assume:
        //   (1) One seek costs 10ms
        //   (2) Writing or reading 1MB costs 10ms (100MB/s)
        //   (3) A compaction of 1MB does 25MB of IO:
        //         1MB read from this level
        //         10-12MB read from next level (boundaries may be misaligned)
        //         10-12MB written to next level
        // This implies that 25 seeks cost the same as the compaction
        // of 1MB of data.  I.e., one seek costs approximately the
        // same as the compaction of 40KB of data.  We are a little
        // conservative and allow approximately one seek for every 16KB
        // of data before triggering a compaction.
        f->allowed_seeks = static_cast<int>((f->file_size / 16384U));
        if (f->allowed_seeks < 100) f->allowed_seeks = 100;
  
        levels_[level].deleted_files.erase(f->number);
        levels_[level].added_files->insert(f);
      }
    }
  
    // Save the current state in *v.
    void SaveTo(Version* v) {
      BySmallestKey cmp;
      cmp.internal_comparator = &vset_->icmp_;
      for (int level = 0; level < config::kNumLevels; level++) {
        // Merge the set of added files with the set of pre-existing files.
        // Drop any deleted files.  Store the result in *v.
        const std::vector<FileMetaData*>& base_files = base_->files_[level];
        std::vector<FileMetaData*>::const_iterator base_iter = base_files.begin();
        std::vector<FileMetaData*>::const_iterator base_end = base_files.end();
        const FileSet* added_files = levels_[level].added_files;
        v->files_[level].reserve(base_files.size() + added_files->size());
        for (const auto& added_file : *added_files) {
          // Add all smaller files listed in base_
          for (std::vector<FileMetaData*>::const_iterator bpos =
                   std::upper_bound(base_iter, base_end, added_file, cmp);
               base_iter != bpos; ++base_iter) {
            MaybeAddFile(v, level, *base_iter);
          }
  
          MaybeAddFile(v, level, added_file);
        }
  
        // Add remaining base files
        for (; base_iter != base_end; ++base_iter) {
          MaybeAddFile(v, level, *base_iter);
        }
  
  #ifndef NDEBUG
        // Make sure there is no overlap in levels > 0
        if (level > 0) {
          for (uint32_t i = 1; i < v->files_[level].size(); i++) {
            const InternalKey& prev_end = v->files_[level][i - 1]->largest;
            const InternalKey& this_begin = v->files_[level][i]->smallest;
            if (vset_->icmp_.Compare(prev_end, this_begin) >= 0) {
              fprintf(stderr, "overlapping ranges in same level %s vs. %s\n",
                      prev_end.DebugString().c_str(),
                      this_begin.DebugString().c_str());
              abort();
            }
          }
        }
  #endif
      }
    }
  
    void MaybeAddFile(Version* v, int level, FileMetaData* f) {
      if (levels_[level].deleted_files.count(f->number) > 0) {
        // File is deleted: do nothing
      } else {
        std::vector<FileMetaData*>* files = &v->files_[level];
        if (level > 0 && !files->empty()) {
          // Must not overlap
          assert(vset_->icmp_.Compare((*files)[files->size() - 1]->largest,
                                      f->smallest) < 0);
        }
        f->refs++;
        files->push_back(f);
      }
    }
  };
  
  VersionSet::VersionSet(const std::string& dbname, const Options* options,
                         TableCache* table_cache,
                         const InternalKeyComparator* cmp)
      : env_(options->env),
        dbname_(dbname),
        options_(options),
        table_cache_(table_cache),
        icmp_(*cmp),
        next_file_number_(2),
        manifest_file_number_(0),  // Filled by Recover()
        last_sequence_(0),
        log_number_(0),
        prev_log_number_(0),
        descriptor_file_(nullptr),
        descriptor_log_(nullptr),
        dummy_versions_(this),
        current_(nullptr) {
    AppendVersion(new Version(this));
  }
  
  VersionSet::~VersionSet() {
    current_->Unref();
    assert(dummy_versions_.next_ == &dummy_versions_);  // List must be empty
    delete descriptor_log_;
    delete descriptor_file_;
  }
  
  void VersionSet::AppendVersion(Version* v) {
    // Make "v" current
    assert(v->refs_ == 0);
    assert(v != current_);
    if (current_ != nullptr) {
      current_->Unref();
    }
    current_ = v;
    v->Ref();
  
    // Append to linked list
    v->prev_ = dummy_versions_.prev_;
    v->next_ = &dummy_versions_;
    v->prev_->next_ = v;
    v->next_->prev_ = v;
  }
  
  
  //::young: LogAndApply() function
  Status VersionSet::LogAndApply(VersionEdit* edit, port::Mutex* mu) {
    if (edit->has_log_number_) {
      assert(edit->log_number_ >= log_number_);
      assert(edit->log_number_ < next_file_number_);
    } else {
      edit->SetLogNumber(log_number_);
    }
  
    if (!edit->has_prev_log_number_) {
      edit->SetPrevLogNumber(prev_log_number_);
    }
  
    edit->SetNextFile(next_file_number_);
    edit->SetLastSequence(last_sequence_);
  
    Version* v = new Version(this);
    {
      Builder builder(this, current_);
      builder.Apply(edit);
      builder.SaveTo(v);
    }
    Finalize(v);
  
    // Initialize new descriptor log file if necessary by creating
    // a temporary file that contains a snapshot of the current version.
    std::string new_manifest_file;
    Status s;
    if (descriptor_log_ == nullptr) {
      // No reason to unlock *mu here since we only hit this path in the
      // first call to LogAndApply (when opening the database).
      assert(descriptor_file_ == nullptr);
      new_manifest_file = DescriptorFileName(dbname_, manifest_file_number_);
      edit->SetNextFile(next_file_number_);
      //::young::
      s = env_->NewWritableFile(new_manifest_file, &descriptor_file_);
      if (s.ok()) {
        descriptor_log_ = new log::Writer(descriptor_file_);
        s = WriteSnapshot(descriptor_log_);
      }
    }
  
    // Unlock during expensive MANIFEST log write
    {
      mu->Unlock();
  
      // Write new record to MANIFEST log
      if (s.ok()) {
        std::string record;
  	//::young:: record is data file????
        edit->EncodeTo(&record);
  	//::young::LogAndApply, flush point (call AddRecord())
        s = descriptor_log_->AddRecord(record); //flushing
        if (s.ok()) {
  	//::young::LogAndApply, sync point
          s = descriptor_file_->Sync();
        }
        if (!s.ok()) {
          Log(options_->info_log, "MANIFEST write: %s\n", s.ToString().c_str());
        }
      }
  
      // If we just created a new descriptor file, install it by writing a
      // new CURRENT file that points to it.
      if (s.ok() && !new_manifest_file.empty()) {
        s = SetCurrentFile(env_, dbname_, manifest_file_number_);
      }
  
      mu->Lock();
    }
  
    // Install the new version
    if (s.ok()) {
      AppendVersion(v);
      log_number_ = edit->log_number_;
      prev_log_number_ = edit->prev_log_number_;
    } else {
      delete v;
      if (!new_manifest_file.empty()) {
        delete descriptor_log_;
        delete descriptor_file_;
        descriptor_log_ = nullptr;
        descriptor_file_ = nullptr;
        env_->RemoveFile(new_manifest_file);
      }
    }
  
    return s;
  }
  
  Status VersionSet::Recover(bool* save_manifest) {
    struct LogReporter : public log::Reader::Reporter {
      Status* status;
      void Corruption(size_t bytes, const Status& s) override {
        if (this->status->ok()) *this->status = s;
      }
    };
  
    // Read "CURRENT" file, which contains a pointer to the current manifest file
    std::string current;
    Status s = ReadFileToString(env_, CurrentFileName(dbname_), &current);
    if (!s.ok()) {
      return s;
    }
    if (current.empty() || current[current.size() - 1] != '\n') {
      return Status::Corruption("CURRENT file does not end with newline");
    }
    current.resize(current.size() - 1);
  
    std::string dscname = dbname_ + "/" + current;
    SequentialFile* file;
    s = env_->NewSequentialFile(dscname, &file);
    if (!s.ok()) {
      if (s.IsNotFound()) {
        return Status::Corruption("CURRENT points to a non-existent file",
                                  s.ToString());
      }
      return s;
    }
  
    bool have_log_number = false;
    bool have_prev_log_number = false;
    bool have_next_file = false;
    bool have_last_sequence = false;
    uint64_t next_file = 0;
    uint64_t last_sequence = 0;
    uint64_t log_number = 0;
    uint64_t prev_log_number = 0;
    Builder builder(this, current_);
  
    {
      LogReporter reporter;
      reporter.status = &s;
      log::Reader reader(file, &reporter, true /*checksum*/,
                         0 /*initial_offset*/);
      Slice record;
      std::string scratch;
      while (reader.ReadRecord(&record, &scratch) && s.ok()) {
        VersionEdit edit;
        s = edit.DecodeFrom(record);
        if (s.ok()) {
          if (edit.has_comparator_ &&
              edit.comparator_ != icmp_.user_comparator()->Name()) {
            s = Status::InvalidArgument(
                edit.comparator_ + " does not match existing comparator ",
                icmp_.user_comparator()->Name());
          }
        }
  
        if (s.ok()) {
          builder.Apply(&edit);
        }
  
        if (edit.has_log_number_) {
          log_number = edit.log_number_;
          have_log_number = true;
        }
  
        if (edit.has_prev_log_number_) {
          prev_log_number = edit.prev_log_number_;
          have_prev_log_number = true;
        }
  
        if (edit.has_next_file_number_) {
          next_file = edit.next_file_number_;
          have_next_file = true;
        }
  
        if (edit.has_last_sequence_) {
          last_sequence = edit.last_sequence_;
          have_last_sequence = true;
        }
      }
    }
    delete file;
    file = nullptr;
  
    if (s.ok()) {
      if (!have_next_file) {
        s = Status::Corruption("no meta-nextfile entry in descriptor");
      } else if (!have_log_number) {
        s = Status::Corruption("no meta-lognumber entry in descriptor");
      } else if (!have_last_sequence) {
        s = Status::Corruption("no last-sequence-number entry in descriptor");
      }
  
      if (!have_prev_log_number) {
        prev_log_number = 0;
      }
  
      MarkFileNumberUsed(prev_log_number);
      MarkFileNumberUsed(log_number);
    }
  
    if (s.ok()) {
      Version* v = new Version(this);
      builder.SaveTo(v);
      // Install recovered version
      Finalize(v);
      AppendVersion(v);
      manifest_file_number_ = next_file;
      next_file_number_ = next_file + 1;
      last_sequence_ = last_sequence;
      log_number_ = log_number;
      prev_log_number_ = prev_log_number;
  
      // See if we can reuse the existing MANIFEST file.
      if (ReuseManifest(dscname, current)) {
        // No need to save new manifest
      } else {
        *save_manifest = true;
      }
    }
  
    return s;
  }
  
  bool VersionSet::ReuseManifest(const std::string& dscname,
                                 const std::string& dscbase) {
    if (!options_->reuse_logs) {
      return false;
    }
    FileType manifest_type;
    uint64_t manifest_number;
    uint64_t manifest_size;
    if (!ParseFileName(dscbase, &manifest_number, &manifest_type) ||
        manifest_type != kDescriptorFile ||
        !env_->GetFileSize(dscname, &manifest_size).ok() ||
        // Make new compacted MANIFEST if old one is too big
        manifest_size >= TargetFileSize(options_)) {
      return false;
    }
  
    assert(descriptor_file_ == nullptr);
    assert(descriptor_log_ == nullptr);
    Status r = env_->NewAppendableFile(dscname, &descriptor_file_);
    if (!r.ok()) {
      Log(options_->info_log, "Reuse MANIFEST: %s\n", r.ToString().c_str());
      assert(descriptor_file_ == nullptr);
      return false;
    }
  
    Log(options_->info_log, "Reusing MANIFEST %s\n", dscname.c_str());
    descriptor_log_ = new log::Writer(descriptor_file_, manifest_size);
    manifest_file_number_ = manifest_number;
    return true;
  }
  
  void VersionSet::MarkFileNumberUsed(uint64_t number) {
    if (next_file_number_ <= number) {
      next_file_number_ = number + 1;
    }
  }
  
  void VersionSet::Finalize(Version* v) {
    // Precomputed best level for next compaction
    int best_level = -1;
    double best_score = -1;
  
    //::young::select next compaction level 
    for (int level = 0; level < config::kNumLevels - 1; level++) {
      double score;
      if (level == 0) {
        // We treat level-0 specially by bounding the number of files
        // instead of number of bytes for two reasons:
        //
        // (1) With larger write-buffer sizes, it is nice not to do too
        // many level-0 compactions.
        //
        // (2) The files in level-0 are merged on every read and
        // therefore we wish to avoid too many files when the individual
        // file size is small (perhaps because of a small write-buffer
        // setting, or very high compression ratios, or lots of
        // overwrites/deletions).
        score = v->files_[level].size() /
                static_cast<double>(config::kL0_CompactionTrigger);
      } else {
        // Compute the ratio of current size to size limit.
        const uint64_t level_bytes = TotalFileSize(v->files_[level]);
        score =
            static_cast<double>(level_bytes) / MaxBytesForLevel(options_, level);
      }
  
      if (score > best_score) {
        best_level = level;
        best_score = score;
      }
    }
  
    v->compaction_level_ = best_level;
    v->compaction_score_ = best_score;
  }
  
  
  //::young:: write snaptshot
  Status VersionSet::WriteSnapshot(log::Writer* log) {
    // TODO: Break up into multiple records to reduce memory usage on recovery?
  
    // Save metadata
    VersionEdit edit;
    edit.SetComparatorName(icmp_.user_comparator()->Name());
  
    // Save compaction pointers
    for (int level = 0; level < config::kNumLevels; level++) {
      if (!compact_pointer_[level].empty()) {
        InternalKey key;
        key.DecodeFrom(compact_pointer_[level]);
        edit.SetCompactPointer(level, key);
      }
    }
  
    // Save files
    for (int level = 0; level < config::kNumLevels; level++) {
      const std::vector<FileMetaData*>& files = current_->files_[level];
      for (size_t i = 0; i < files.size(); i++) {
        const FileMetaData* f = files[i];
        edit.AddFile(level, f->number, f->file_size, f->smallest, f->largest);
      }
    }
  
    std::string record;
    edit.EncodeTo(&record);
    return log->AddRecord(record);
  }
  
  int VersionSet::NumLevelFiles(int level) const {
    assert(level >= 0);
    assert(level < config::kNumLevels);
    return current_->files_[level].size();
  }
  
  const char* VersionSet::LevelSummary(LevelSummaryStorage* scratch) const {
    // Update code if kNumLevels changes
    static_assert(config::kNumLevels == 7, "");
    snprintf(scratch->buffer, sizeof(scratch->buffer),
             "files[ %d %d %d %d %d %d %d ]", int(current_->files_[0].size()),
             int(current_->files_[1].size()), int(current_->files_[2].size()),
             int(current_->files_[3].size()), int(current_->files_[4].size()),
             int(current_->files_[5].size()), int(current_->files_[6].size()));
    return scratch->buffer;
  }
  
  uint64_t VersionSet::ApproximateOffsetOf(Version* v, const InternalKey& ikey) {
    uint64_t result = 0;
    for (int level = 0; level < config::kNumLevels; level++) {
      const std::vector<FileMetaData*>& files = v->files_[level];
      for (size_t i = 0; i < files.size(); i++) {
        if (icmp_.Compare(files[i]->largest, ikey) <= 0) {
          // Entire file is before "ikey", so just add the file size
          result += files[i]->file_size;
        } else if (icmp_.Compare(files[i]->smallest, ikey) > 0) {
          // Entire file is after "ikey", so ignore
          if (level > 0) {
            // Files other than level 0 are sorted by meta->smallest, so
            // no further files in this level will contain data for
            // "ikey".
            break;
          }
        } else {
          // "ikey" falls in the range for this table.  Add the
          // approximate offset of "ikey" within the table.
          Table* tableptr;
          Iterator* iter = table_cache_->NewIterator(
              ReadOptions(), files[i]->number, files[i]->file_size, &tableptr);
          if (tableptr != nullptr) {
            result += tableptr->ApproximateOffsetOf(ikey.Encode());
          }
          delete iter;
        }
      }
    }
    return result;
  }
  
  void VersionSet::AddLiveFiles(std::set<uint64_t>* live) {
    for (Version* v = dummy_versions_.next_; v != &dummy_versions_;
         v = v->next_) {
      for (int level = 0; level < config::kNumLevels; level++) {
        const std::vector<FileMetaData*>& files = v->files_[level];
        for (size_t i = 0; i < files.size(); i++) {
          live->insert(files[i]->number);
        }
      }
    }
  }
  
  int64_t VersionSet::NumLevelBytes(int level) const {
    assert(level >= 0);
    assert(level < config::kNumLevels);
    return TotalFileSize(current_->files_[level]);
  }
  
  int64_t VersionSet::MaxNextLevelOverlappingBytes() {
    int64_t result = 0;
    std::vector<FileMetaData*> overlaps;
    for (int level = 1; level < config::kNumLevels - 1; level++) {
      for (size_t i = 0; i < current_->files_[level].size(); i++) {
        const FileMetaData* f = current_->files_[level][i];
        current_->GetOverlappingInputs(level + 1, &f->smallest, &f->largest,
                                       &overlaps);
        const int64_t sum = TotalFileSize(overlaps);
        if (sum > result) {
          result = sum;
        }
      }
    }
    return result;
  }
  
  // Stores the minimal range that covers all entries in inputs in
  // *smallest, *largest.
  // REQUIRES: inputs is not empty
  void VersionSet::GetRange(const std::vector<FileMetaData*>& inputs,
                            InternalKey* smallest, InternalKey* largest) {
    assert(!inputs.empty());
    smallest->Clear();
    largest->Clear();
    for (size_t i = 0; i < inputs.size(); i++) {
      FileMetaData* f = inputs[i];
      if (i == 0) {
        *smallest = f->smallest;
        *largest = f->largest;
      } else {
        if (icmp_.Compare(f->smallest, *smallest) < 0) {
          *smallest = f->smallest;
        }
        if (icmp_.Compare(f->largest, *largest) > 0) {
          *largest = f->largest;
        }
      }
    }
  }
  
  // Stores the minimal range that covers all entries in inputs1 and inputs2
  // in *smallest, *largest.
  // REQUIRES: inputs is not empty
  void VersionSet::GetRange2(const std::vector<FileMetaData*>& inputs1,
                             const std::vector<FileMetaData*>& inputs2,
                             InternalKey* smallest, InternalKey* largest) {
    std::vector<FileMetaData*> all = inputs1;
    all.insert(all.end(), inputs2.begin(), inputs2.end());
    GetRange(all, smallest, largest);
  }
  
  Iterator* VersionSet::MakeInputIterator(Compaction* c) {
    ReadOptions options;
    options.verify_checksums = options_->paranoid_checks;
    options.fill_cache = false;
  
    // Level-0 files have to be merged together.  For other levels,
    // we will make a concatenating iterator per level.
    // TODO(opt): use concatenating iterator for level-0 if there is no overlap
    const int space = (c->level() == 0 ? c->inputs_[0].size() + 1 : 2);
    Iterator** list = new Iterator*[space];
    int num = 0;
    for (int which = 0; which < 2; which++) {
      if (!c->inputs_[which].empty()) {
        if (c->level() + which == 0) {
          const std::vector<FileMetaData*>& files = c->inputs_[which];
          for (size_t i = 0; i < files.size(); i++) {
            list[num++] = table_cache_->NewIterator(options, files[i]->number,
                                                    files[i]->file_size);
          }
        } else {
          // Create concatenating iterator for the files from this level
          list[num++] = NewTwoLevelIterator(
              new Version::LevelFileNumIterator(icmp_, &c->inputs_[which]),
              &GetFileIterator, table_cache_, options);
        }
      }
    }
    assert(num <= space);
    Iterator* result = NewMergingIterator(&icmp_, list, num);
    delete[] list;
    return result;
  }
  
  Compaction* VersionSet::PickCompaction() {
    Compaction* c;
    int level;
  
    // We prefer compactions triggered by too much data in a level over
    // the compactions triggered by seeks.
    const bool size_compaction = (current_->compaction_score_ >= 1);
    const bool seek_compaction = (current_->file_to_compact_ != nullptr);
    if (size_compaction) {
      level = current_->compaction_level_;
      assert(level >= 0);
      assert(level + 1 < config::kNumLevels);
      c = new Compaction(options_, level);
  
      // Pick the first file that comes after compact_pointer_[level]
      for (size_t i = 0; i < current_->files_[level].size(); i++) {
        FileMetaData* f = current_->files_[level][i];
        if (compact_pointer_[level].empty() ||
            icmp_.Compare(f->largest.Encode(), compact_pointer_[level]) > 0) {
          c->inputs_[0].push_back(f);
          break;
        }
      }
      if (c->inputs_[0].empty()) {
        // Wrap-around to the beginning of the key space
        c->inputs_[0].push_back(current_->files_[level][0]);
      }
    } else if (seek_compaction) {
      level = current_->file_to_compact_level_;
      c = new Compaction(options_, level);
      c->inputs_[0].push_back(current_->file_to_compact_);
    } else {
      return nullptr;
    }
  
    c->input_version_ = current_;
    c->input_version_->Ref();
  
    // Files in level 0 may overlap each other, so pick up all overlapping ones
    if (level == 0) {
      InternalKey smallest, largest;
      GetRange(c->inputs_[0], &smallest, &largest);
      // Note that the next call will discard the file we placed in
      // c->inputs_[0] earlier and replace it with an overlapping set
      // which will include the picked file.
      current_->GetOverlappingInputs(0, &smallest, &largest, &c->inputs_[0]);
      assert(!c->inputs_[0].empty());
    }
  
    SetupOtherInputs(c);
  
    return c;
  }
  
  // Finds the largest key in a vector of files. Returns true if files it not
  // empty.
  bool FindLargestKey(const InternalKeyComparator& icmp,
                      const std::vector<FileMetaData*>& files,
                      InternalKey* largest_key) {
    if (files.empty()) {
      return false;
    }
    *largest_key = files[0]->largest;
    for (size_t i = 1; i < files.size(); ++i) {
      FileMetaData* f = files[i];
      if (icmp.Compare(f->largest, *largest_key) > 0) {
        *largest_key = f->largest;
      }
    }
    return true;
  }
  
  // Finds minimum file b2=(l2, u2) in level file for which l2 > u1 and
  // user_key(l2) = user_key(u1)
  FileMetaData* FindSmallestBoundaryFile(
      const InternalKeyComparator& icmp,
      const std::vector<FileMetaData*>& level_files,
      const InternalKey& largest_key) {
    const Comparator* user_cmp = icmp.user_comparator();
    FileMetaData* smallest_boundary_file = nullptr;
    for (size_t i = 0; i < level_files.size(); ++i) {
      FileMetaData* f = level_files[i];
      if (icmp.Compare(f->smallest, largest_key) > 0 &&
          user_cmp->Compare(f->smallest.user_key(), largest_key.user_key()) ==
              0) {
        if (smallest_boundary_file == nullptr ||
            icmp.Compare(f->smallest, smallest_boundary_file->smallest) < 0) {
          smallest_boundary_file = f;
        }
      }
    }
    return smallest_boundary_file;
  }
  
  // Extracts the largest file b1 from |compaction_files| and then searches for a
  // b2 in |level_files| for which user_key(u1) = user_key(l2). If it finds such a
  // file b2 (known as a boundary file) it adds it to |compaction_files| and then
  // searches again using this new upper bound.
  //
  // If there are two blocks, b1=(l1, u1) and b2=(l2, u2) and
  // user_key(u1) = user_key(l2), and if we compact b1 but not b2 then a
  // subsequent get operation will yield an incorrect result because it will
  // return the record from b2 in level i rather than from b1 because it searches
  // level by level for records matching the supplied user key.
  //
  // parameters:
  //   in     level_files:      List of files to search for boundary files.
  //   in/out compaction_files: List of files to extend by adding boundary files.
  void AddBoundaryInputs(const InternalKeyComparator& icmp,
                         const std::vector<FileMetaData*>& level_files,
                         std::vector<FileMetaData*>* compaction_files) {
    InternalKey largest_key;
  
    // Quick return if compaction_files is empty.
    if (!FindLargestKey(icmp, *compaction_files, &largest_key)) {
      return;
    }
  
    bool continue_searching = true;
    while (continue_searching) {
      FileMetaData* smallest_boundary_file =
          FindSmallestBoundaryFile(icmp, level_files, largest_key);
  
      // If a boundary file was found advance largest_key, otherwise we're done.
      if (smallest_boundary_file != NULL) {
        compaction_files->push_back(smallest_boundary_file);
        largest_key = smallest_boundary_file->largest;
      } else {
        continue_searching = false;
      }
    }
  }
  
  void VersionSet::SetupOtherInputs(Compaction* c) {
    const int level = c->level();
    InternalKey smallest, largest;
  
    AddBoundaryInputs(icmp_, current_->files_[level], &c->inputs_[0]);
    GetRange(c->inputs_[0], &smallest, &largest);
  
    current_->GetOverlappingInputs(level + 1, &smallest, &largest,
                                   &c->inputs_[1]);
  
    // Get entire range covered by compaction
    InternalKey all_start, all_limit;
    GetRange2(c->inputs_[0], c->inputs_[1], &all_start, &all_limit);
  
    // See if we can grow the number of inputs in "level" without
    // changing the number of "level+1" files we pick up.
    if (!c->inputs_[1].empty()) {
      std::vector<FileMetaData*> expanded0;
      current_->GetOverlappingInputs(level, &all_start, &all_limit, &expanded0);
      AddBoundaryInputs(icmp_, current_->files_[level], &expanded0);
      const int64_t inputs0_size = TotalFileSize(c->inputs_[0]);
      const int64_t inputs1_size = TotalFileSize(c->inputs_[1]);
      const int64_t expanded0_size = TotalFileSize(expanded0);
      if (expanded0.size() > c->inputs_[0].size() &&
          inputs1_size + expanded0_size <
              ExpandedCompactionByteSizeLimit(options_)) {
        InternalKey new_start, new_limit;
        GetRange(expanded0, &new_start, &new_limit);
        std::vector<FileMetaData*> expanded1;
        current_->GetOverlappingInputs(level + 1, &new_start, &new_limit,
                                       &expanded1);
        if (expanded1.size() == c->inputs_[1].size()) {
          Log(options_->info_log,
              "Expanding@%d %d+%d (%ld+%ld bytes) to %d+%d (%ld+%ld bytes)\n",
              level, int(c->inputs_[0].size()), int(c->inputs_[1].size()),
              long(inputs0_size), long(inputs1_size), int(expanded0.size()),
              int(expanded1.size()), long(expanded0_size), long(inputs1_size));
          smallest = new_start;
          largest = new_limit;
          c->inputs_[0] = expanded0;
          c->inputs_[1] = expanded1;
          GetRange2(c->inputs_[0], c->inputs_[1], &all_start, &all_limit);
        }
      }
    }
  
    // Compute the set of grandparent files that overlap this compaction
    // (parent == level+1; grandparent == level+2)
    if (level + 2 < config::kNumLevels) {
      current_->GetOverlappingInputs(level + 2, &all_start, &all_limit,
                                     &c->grandparents_);
    }
  
    // Update the place where we will do the next compaction for this level.
    // We update this immediately instead of waiting for the VersionEdit
    // to be applied so that if the compaction fails, we will try a different
    // key range next time.
    compact_pointer_[level] = largest.Encode().ToString();
    c->edit_.SetCompactPointer(level, largest);
  }
  
  Compaction* VersionSet::CompactRange(int level, const InternalKey* begin,
                                       const InternalKey* end) {
    std::vector<FileMetaData*> inputs;
    current_->GetOverlappingInputs(level, begin, end, &inputs);
    if (inputs.empty()) {
      return nullptr;
    }
  
    // Avoid compacting too much in one shot in case the range is large.
    // But we cannot do this for level-0 since level-0 files can overlap
    // and we must not pick one file and drop another older file if the
    // two files overlap.
    if (level > 0) {
      const uint64_t limit = MaxFileSizeForLevel(options_, level);
      uint64_t total = 0;
      for (size_t i = 0; i < inputs.size(); i++) {
        uint64_t s = inputs[i]->file_size;
        total += s;
        if (total >= limit) {
          inputs.resize(i + 1);
          break;
        }
      }
    }
  
    Compaction* c = new Compaction(options_, level);
    c->input_version_ = current_;
    c->input_version_->Ref();
    c->inputs_[0] = inputs;
    SetupOtherInputs(c);
    return c;
  }
  
  Compaction::Compaction(const Options* options, int level)
      : level_(level),
        max_output_file_size_(MaxFileSizeForLevel(options, level)),
        input_version_(nullptr),
        grandparent_index_(0),
        seen_key_(false),
        overlapped_bytes_(0) {
    for (int i = 0; i < config::kNumLevels; i++) {
      level_ptrs_[i] = 0;
    }
  }
  
  Compaction::~Compaction() {
    if (input_version_ != nullptr) {
      input_version_->Unref();
    }
  }
  
  bool Compaction::IsTrivialMove() const {
    const VersionSet* vset = input_version_->vset_;
    // Avoid a move if there is lots of overlapping grandparent data.
    // Otherwise, the move could create a parent file that will require
    // a very expensive merge later on.
    return (num_input_files(0) == 1 && num_input_files(1) == 0 &&
            TotalFileSize(grandparents_) <=
                MaxGrandParentOverlapBytes(vset->options_));
  }
  
  void Compaction::AddInputDeletions(VersionEdit* edit) {
    for (int which = 0; which < 2; which++) {
      for (size_t i = 0; i < inputs_[which].size(); i++) {
        edit->RemoveFile(level_ + which, inputs_[which][i]->number);
      }
    }
  }
  
  bool Compaction::IsBaseLevelForKey(const Slice& user_key) {
    // Maybe use binary search to find right entry instead of linear search?
    const Comparator* user_cmp = input_version_->vset_->icmp_.user_comparator();
    for (int lvl = level_ + 2; lvl < config::kNumLevels; lvl++) {
      const std::vector<FileMetaData*>& files = input_version_->files_[lvl];
      while (level_ptrs_[lvl] < files.size()) {
        FileMetaData* f = files[level_ptrs_[lvl]];
        if (user_cmp->Compare(user_key, f->largest.user_key()) <= 0) {
          // We've advanced far enough
          if (user_cmp->Compare(user_key, f->smallest.user_key()) >= 0) {
            // Key falls in this file's range, so definitely not base level
            return false;
          }
          break;
        }
        level_ptrs_[lvl]++;
      }
    }
    return true;
  }
  
  bool Compaction::ShouldStopBefore(const Slice& internal_key) {
    const VersionSet* vset = input_version_->vset_;
    // Scan to find earliest grandparent file that contains key.
    const InternalKeyComparator* icmp = &vset->icmp_;
    while (grandparent_index_ < grandparents_.size() &&
           icmp->Compare(internal_key,
                         grandparents_[grandparent_index_]->largest.Encode()) >
               0) {
      if (seen_key_) {
        overlapped_bytes_ += grandparents_[grandparent_index_]->file_size;
      }
      grandparent_index_++;
    }
    seen_key_ = true;
  
    if (overlapped_bytes_ > MaxGrandParentOverlapBytes(vset->options_)) {
      // Too much overlap for current output; start new output
      overlapped_bytes_ = 0;
      return true;
    } else {
      return false;
    }
  }
  
  void Compaction::ReleaseInputs() {
    if (input_version_ != nullptr) {
      input_version_->Unref();
      input_version_ = nullptr;
    }
  }
  
  }  // namespace leveldb
  