Inside Bitcoin

501  if (begin != nullptr) {
502    user_begin = begin->user_key();
503  }
504  if (end != nullptr) {
505    user_end = end->user_key();
506  }
507  const Comparator* user_cmp = vset_->icmp_.user_comparator();
508  for (size_t i = 0; i < files_[level].size();) {
509    FileMetaData* f = files_[level][i++];
510    const Slice file_start = f->smallest.user_key();
511    const Slice file_limit = f->largest.user_key();
512    if (begin != nullptr && user_cmp->Compare(file_limit, user_begin) < 0) {
513      // "f" is completely before specified range; skip it
514    } else if (end != nullptr && user_cmp->Compare(file_start, user_end) > 0) {
515      // "f" is completely after specified range; skip it
516    } else {
517      inputs->push_back(f);
518      if (level == 0) {
519        // Level-0 files may overlap each other.  So check if the newly
520        // added file has expanded the range.  If so, restart search.
521        if (begin != nullptr && user_cmp->Compare(file_start, user_begin) < 0) {
522          user_begin = file_start;
523          inputs->clear();
524          i = 0;
525        } else if (end != nullptr &&
526                   user_cmp->Compare(file_limit, user_end) > 0) {
527          user_end = file_limit;
528          inputs->clear();
529          i = 0;
530        }
531      }
532    }
533  }
534}
535
536std::string Version::DebugString() const {
537  std::string r;
538  for (int level = 0; level < config::kNumLevels; level++) {
539    // E.g.,
540    //   --- level 1 ---
541    //   17:123['a' .. 'd']
542    //   20:43['e' .. 'g']
543    r.append("--- level ");
544    AppendNumberTo(&r, level);
545    r.append(" ---\n");
546    const std::vector<FileMetaData*>& files = files_[level];
547    for (size_t i = 0; i < files.size(); i++) {
548      r.push_back(' ');
549      AppendNumberTo(&r, files[i]->number);
550      r.push_back(':');
551      AppendNumberTo(&r, files[i]->file_size);
552      r.append("[");
553      r.append(files[i]->smallest.DebugString());
554      r.append(" .. ");
555      r.append(files[i]->largest.DebugString());
556      r.append("]\n");
557    }
558  }
559  return r;
560}
561
562// A helper class so we can efficiently apply a whole sequence
563// of edits to a particular state without creating intermediate
564// Versions that contain full copies of the intermediate state.
565class VersionSet::Builder {
566 private:
567  // Helper to sort by v->files_[file_number].smallest
568  struct BySmallestKey {
569    const InternalKeyComparator* internal_comparator;
570
571    bool operator()(FileMetaData* f1, FileMetaData* f2) const {
572      int r = internal_comparator->Compare(f1->smallest, f2->smallest);
573      if (r != 0) {
574        return (r < 0);
575      } else {
576        // Break ties by file number
577        return (f1->number < f2->number);
578      }
579    }
580  };
581
582  typedef std::set<FileMetaData*, BySmallestKey> FileSet;
583  struct LevelState {
584    std::set<uint64_t> deleted_files;
585    FileSet* added_files;
586  };
587
588  VersionSet* vset_;
589  Version* base_;
590  LevelState levels_[config::kNumLevels];
591
592 public:
593  // Initialize a builder with the files from *base and other info from *vset
594  Builder(VersionSet* vset, Version* base) : vset_(vset), base_(base) {
595    base_->Ref();
596    BySmallestKey cmp;
597    cmp.internal_comparator = &vset_->icmp_;
598    for (int level = 0; level < config::kNumLevels; level++) {
599      levels_[level].added_files = new FileSet(cmp);
600    }
601  }
602
603  ~Builder() {
604    for (int level = 0; level < config::kNumLevels; level++) {
605      const FileSet* added = levels_[level].added_files;
606      std::vector<FileMetaData*> to_unref;
607      to_unref.reserve(added->size());
608      for (FileSet::const_iterator it = added->begin(); it != added->end();
609           ++it) {
610        to_unref.push_back(*it);
611      }
612      delete added;
613      for (uint32_t i = 0; i < to_unref.size(); i++) {
614        FileMetaData* f = to_unref[i];
615        f->refs--;
616        if (f->refs <= 0) {
617          delete f;
618        }
619      }
620    }
621    base_->Unref();
622  }
623
624  // Apply all of the edits in *edit to the current state.
625  void Apply(VersionEdit* edit) {
626    // Update compaction pointers
627    for (size_t i = 0; i < edit->compact_pointers_.size(); i++) {
628      const int level = edit->compact_pointers_[i].first;
629      vset_->compact_pointer_[level] =
630          edit->compact_pointers_[i].second.Encode().ToString();
631    }
632
633    // Delete files
634    for (const auto& deleted_file_set_kvp : edit->deleted_files_) {
635      const int level = deleted_file_set_kvp.first;
636      const uint64_t number = deleted_file_set_kvp.second;
637      levels_[level].deleted_files.insert(number);
638    }
639
640    // Add new files
641    for (size_t i = 0; i < edit->new_files_.size(); i++) {
642      const int level = edit->new_files_[i].first;
643      FileMetaData* f = new FileMetaData(edit->new_files_[i].second);
644      f->refs = 1;
645
646      // We arrange to automatically compact this file after
647      // a certain number of seeks.  Let's assume:
648      //   (1) One seek costs 10ms
649      //   (2) Writing or reading 1MB costs 10ms (100MB/s)
650      //   (3) A compaction of 1MB does 25MB of IO:
651      //         1MB read from this level
652      //         10-12MB read from next level (boundaries may be misaligned)
653      //         10-12MB written to next level
654      // This implies that 25 seeks cost the same as the compaction
655      // of 1MB of data.  I.e., one seek costs approximately the
656      // same as the compaction of 40KB of data.  We are a little
657      // conservative and allow approximately one seek for every 16KB
658      // of data before triggering a compaction.
659      //
660      // Note: seek compactions are disabled. See Version::UpdateStats.
661      f->allowed_seeks = static_cast<int>((f->file_size / 16384U));
662      if (f->allowed_seeks < 100) f->allowed_seeks = 100;
663
664      levels_[level].deleted_files.erase(f->number);
665      levels_[level].added_files->insert(f);
666    }
667  }
668
669  // Save the current state in *v.
670  void SaveTo(Version* v) {
671    BySmallestKey cmp;
672    cmp.internal_comparator = &vset_->icmp_;
673    for (int level = 0; level < config::kNumLevels; level++) {
674      // Merge the set of added files with the set of pre-existing files.
675      // Drop any deleted files.  Store the result in *v.
676      const std::vector<FileMetaData*>& base_files = base_->files_[level];
677      std::vector<FileMetaData*>::const_iterator base_iter = base_files.begin();
678      std::vector<FileMetaData*>::const_iterator base_end = base_files.end();
679      const FileSet* added_files = levels_[level].added_files;
680      v->files_[level].reserve(base_files.size() + added_files->size());
681      for (const auto& added_file : *added_files) {
682        // Add all smaller files listed in base_
683        for (std::vector<FileMetaData*>::const_iterator bpos =
684                 std::upper_bound(base_iter, base_end, added_file, cmp);
685             base_iter != bpos; ++base_iter) {
686          MaybeAddFile(v, level, *base_iter);
687        }
688
689        MaybeAddFile(v, level, added_file);
690      }
691
692      // Add remaining base files
693      for (; base_iter != base_end; ++base_iter) {
694        MaybeAddFile(v, level, *base_iter);
695      }
696
697#ifndef NDEBUG
698      // Make sure there is no overlap in levels > 0
699      if (level > 0) {
700        for (uint32_t i = 1; i < v->files_[level].size(); i++) {
701          const InternalKey& prev_end = v->files_[level][i - 1]->largest;
702          const InternalKey& this_begin = v->files_[level][i]->smallest;
703          if (vset_->icmp_.Compare(prev_end, this_begin) >= 0) {
704            fprintf(stderr, "overlapping ranges in same level %s vs. %s\n",
705                    prev_end.DebugString().c_str(),
706                    this_begin.DebugString().c_str());
707            abort();
708          }
709        }
710      }
711#endif
712    }
713  }
714
715  void MaybeAddFile(Version* v, int level, FileMetaData* f) {
716    if (levels_[level].deleted_files.count(f->number) > 0) {
717      // File is deleted: do nothing
718    } else {
719      std::vector<FileMetaData*>* files = &v->files_[level];
720      if (level > 0 && !files->empty()) {
721        // Must not overlap
722        assert(vset_->icmp_.Compare((*files)[files->size() - 1]->largest,
723                                    f->smallest) < 0);
724      }
725      f->refs++;
726      files->push_back(f);
727    }
728  }
729};
730
731VersionSet::VersionSet(const std::string& dbname, const Options* options,
732                       TableCache* table_cache,
733                       const InternalKeyComparator* cmp)
734    : env_(options->env),
735      dbname_(dbname),
736      options_(options),
737      table_cache_(table_cache),
738      icmp_(*cmp),
739      next_file_number_(2),
740      manifest_file_number_(0),  // Filled by Recover()
741      last_sequence_(0),
742      log_number_(0),
743      prev_log_number_(0),
744      descriptor_file_(nullptr),
745      descriptor_log_(nullptr),
746      dummy_versions_(this),
747      current_(nullptr) {
748  AppendVersion(new Version(this));
749}
750