version_set.cc | Explore in Territory

// 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 <algorithm>
#include <cstdio>

#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) { … }

// 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) { … }

// 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) { … }

static double MaxBytesForLevel(const Options* options, int level) { … }

static uint64_t MaxFileSizeForLevel(const Options* options, int level) { … }

static int64_t TotalFileSize(const std::vector<FileMetaData*>& files) { … }

Version::~Version() { … }

int FindFile(const InternalKeyComparator& icmp,
             const std::vector<FileMetaData*>& files, const Slice& key) { … }

static bool AfterFile(const Comparator* ucmp, const Slice* user_key,
                      const FileMetaData* f) { … }

static bool BeforeFile(const Comparator* ucmp, const Slice* user_key,
                       const FileMetaData* f) { … }

bool SomeFileOverlapsRange(const InternalKeyComparator& icmp,
                           bool disjoint_sorted_files,
                           const std::vector<FileMetaData*>& files,
                           const Slice* smallest_user_key,
                           const Slice* largest_user_key) { … }

// 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 { … };

static Iterator* GetFileIterator(void* arg, const ReadOptions& options,
                                 const Slice& file_value) { … }

Iterator* Version::NewConcatenatingIterator(const ReadOptions& options,
                                            int level) const { … }

void Version::AddIterators(const ReadOptions& options,
                           std::vector<Iterator*>* iters) { … }

// Callback from TableCache::Get()
namespace {
enum SaverState { … };
struct Saver { … };
}  // namespace
static void SaveValue(void* arg, const Slice& ikey, const Slice& v) { … }

static bool NewestFirst(FileMetaData* a, FileMetaData* b) { … }

void Version::ForEachOverlapping(Slice user_key, Slice internal_key, void* arg,
                                 bool (*func)(void*, int, FileMetaData*)) { … }

Status Version::Get(const ReadOptions& options, const LookupKey& k,
                    std::string* value, GetStats* stats) { … }

bool Version::UpdateStats(const GetStats& stats) { … }

bool Version::RecordReadSample(Slice internal_key) { … }

void Version::Ref() { … }

void Version::Unref() { … }

bool Version::OverlapInLevel(int level, const Slice* smallest_user_key,
                             const Slice* largest_user_key) { … }

int Version::PickLevelForMemTableOutput(const Slice& smallest_user_key,
                                        const Slice& largest_user_key) { … }

// 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) { … }

std::string Version::DebugString() const { … }

// 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 { … };

VersionSet::VersionSet(const std::string& dbname, const Options* options,
                       TableCache* table_cache,
                       const InternalKeyComparator* cmp)
    : … { … }

VersionSet::~VersionSet() { … }

void VersionSet::AppendVersion(Version* v) { … }

Status VersionSet::LogAndApply(VersionEdit* edit, port::Mutex* mu) { … }

Status VersionSet::Recover(bool* save_manifest) { … }

bool VersionSet::ReuseManifest(const std::string& dscname,
                               const std::string& dscbase) { … }

void VersionSet::MarkFileNumberUsed(uint64_t number) { … }

void VersionSet::Finalize(Version* v) { … }

Status VersionSet::WriteSnapshot(log::Writer* log) { … }

int VersionSet::NumLevelFiles(int level) const { … }

const char* VersionSet::LevelSummary(LevelSummaryStorage* scratch) const { … }

uint64_t VersionSet::ApproximateOffsetOf(Version* v, const InternalKey& ikey) { … }

void VersionSet::AddLiveFiles(std::set<uint64_t>* live) { … }

int64_t VersionSet::NumLevelBytes(int level) const { … }

int64_t VersionSet::MaxNextLevelOverlappingBytes() { … }

// 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) { … }

// 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) { … }

Iterator* VersionSet::MakeInputIterator(Compaction* c) { … }

Compaction* VersionSet::PickCompaction() { … }

// Finds the largest key in a vector of files. Returns true if files is not
// empty.
bool FindLargestKey(const InternalKeyComparator& icmp,
                    const std::vector<FileMetaData*>& files,
                    InternalKey* largest_key) { … }

// 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) { … }

// 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) { … }

void VersionSet::SetupOtherInputs(Compaction* c) { … }

Compaction* VersionSet::CompactRange(int level, const InternalKey* begin,
                                     const InternalKey* end) { … }

Compaction::Compaction(const Options* options, int level)
    : … { … }

Compaction::~Compaction() { … }

bool Compaction::IsTrivialMove() const { … }

void Compaction::AddInputDeletions(VersionEdit* edit) { … }

bool Compaction::IsBaseLevelForKey(const Slice& user_key) { … }

bool Compaction::ShouldStopBefore(const Slice& internal_key) { … }

void Compaction::ReleaseInputs() { … }

}  // namespace leveldb
chromium/third_party/leveldatabase/src/db/version_set.cc
