diff options
author | Chris Mumford <cmumford@google.com> | 2019-04-11 19:10:37 -0700 |
---|---|---|
committer | Chris Mumford <cmumford@google.com> | 2019-04-12 00:17:03 -0700 |
commit | 65e86f75ea30e44bc65327f92a16328684269acb (patch) | |
tree | 6f7e0fc9c4a74f2ceee4b938066c486de9bc24e4 /db | |
parent | 7711e76766231bf93e0487c4530b2655e8c4c0b1 (diff) | |
download | leveldb-65e86f75ea30e44bc65327f92a16328684269acb.tar.gz |
Fix formatting of recent snapshot compaction fix.
Fix variable names, line lengths, namespace use, and a few other
minor issues to conform to Google C++ style guide.
PiperOrigin-RevId: 243187729
Diffstat (limited to 'db')
-rw-r--r-- | db/version_set.cc | 95 | ||||
-rw-r--r-- | db/version_set_test.cc | 166 |
2 files changed, 135 insertions, 126 deletions
diff --git a/db/version_set.cc b/db/version_set.cc index 7891dfc..56493ac 100644 --- a/db/version_set.cc +++ b/db/version_set.cc @@ -1347,78 +1347,81 @@ Compaction* VersionSet::PickCompaction() { return c; } -// find 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 *largestKey) { +// 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; } - *largestKey = files[0]->largest; + *largest_key = files[0]->largest; for (size_t i = 1; i < files.size(); ++i) { FileMetaData* f = files[i]; - if (icmp.Compare(f->largest, *largestKey) > 0) { - *largestKey = f->largest; + if (icmp.Compare(f->largest, *largest_key) > 0) { + *largest_key = f->largest; } } return true; } -// find 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*> & levelFiles, - const InternalKey & largestKey) { +// 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* smallestBoundaryFile = NULL; - for (size_t i = 0; i < levelFiles.size(); ++i) { - FileMetaData* f = levelFiles[i]; - if (icmp.Compare(f->smallest, largestKey) > 0 && - user_cmp->Compare(f->smallest.user_key(), largestKey.user_key()) == 0) { - if (smallestBoundaryFile == NULL || - icmp.Compare(f->smallest, smallestBoundaryFile->smallest) < 0) { - smallestBoundaryFile = f; + 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 smallestBoundaryFile; + return smallest_boundary_file; } -// 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. +// 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. // -// This function extracts the largest file b1 from compactionFiles -// and then searches for a b2 in levelFiles for which user_key(u1) = -// user_key(l2). If it finds such a file b2 (known as a boundary file) -// it adds it to compactionFiles 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 levelFiles: list of files to search for boundary files -// in/out compactionFiles: list of files to extend by adding boundary files +// 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*>& levelFiles, - std::vector<FileMetaData*>* compactionFiles) { - InternalKey largestKey; + const std::vector<FileMetaData*>& level_files, + std::vector<FileMetaData*>* compaction_files) { + InternalKey largest_key; - // find largestKey in compactionFiles, quick return if compactionFiles is - // empty - if (!FindLargestKey(icmp, *compactionFiles, &largestKey)) { + // Quick return if compaction_files is empty. + if (!FindLargestKey(icmp, *compaction_files, &largest_key)) { return; } - bool continueSearching = true; - while (continueSearching) { - FileMetaData* smallestBoundaryFile = - FindSmallestBoundaryFile(icmp, levelFiles, largestKey); + bool continue_searching = true; + while (continue_searching) { + FileMetaData* smallest_boundary_file = + FindSmallestBoundaryFile(icmp, level_files, largest_key); - // if a boundary file was found advance largestKey, otherwise we're done - if (smallestBoundaryFile != NULL) { - compactionFiles->push_back(smallestBoundaryFile); - largestKey = smallestBoundaryFile->largest; + // 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 { - continueSearching = false; + continue_searching = false; } } } diff --git a/db/version_set_test.cc b/db/version_set_test.cc index 090f115..b32e2e5 100644 --- a/db/version_set_test.cc +++ b/db/version_set_test.cc @@ -172,154 +172,160 @@ TEST(FindFileTest, OverlappingFiles) { ASSERT_TRUE(Overlaps("600", "700")); } -void AddBoundaryInputs(const InternalKeyComparator &icmp, - const std::vector<FileMetaData *> &levelFiles, - std::vector<FileMetaData *> *compactionFiles); +void AddBoundaryInputs(const InternalKeyComparator& icmp, + const std::vector<FileMetaData*>& level_files, + std::vector<FileMetaData*>* compaction_files); class AddBoundaryInputsTest { public: - std::vector<FileMetaData *> levelFiles_; - std::vector<FileMetaData *> compactionFiles_; - std::vector<FileMetaData *> allFiles_; + std::vector<FileMetaData*> level_files_; + std::vector<FileMetaData*> compaction_files_; + std::vector<FileMetaData*> all_files_; InternalKeyComparator icmp_; AddBoundaryInputsTest() : icmp_(BytewiseComparator()){}; ~AddBoundaryInputsTest() { - for (size_t i = 0; i < allFiles_.size(); ++i) { - delete allFiles_[i]; + for (size_t i = 0; i < all_files_.size(); ++i) { + delete all_files_[i]; } - allFiles_.clear(); + all_files_.clear(); }; - FileMetaData *CreateFileMetaData(uint64_t number, InternalKey smallest, + FileMetaData* CreateFileMetaData(uint64_t number, InternalKey smallest, InternalKey largest) { - FileMetaData *f = new FileMetaData(); + FileMetaData* f = new FileMetaData(); f->number = number; f->smallest = smallest; f->largest = largest; - allFiles_.push_back(f); + all_files_.push_back(f); return f; } }; TEST(AddBoundaryInputsTest, TestEmptyFileSets) { - AddBoundaryInputs(icmp_, levelFiles_, &compactionFiles_); - ASSERT_TRUE(compactionFiles_.empty()); - ASSERT_TRUE(levelFiles_.empty()); + AddBoundaryInputs(icmp_, level_files_, &compaction_files_); + ASSERT_TRUE(compaction_files_.empty()); + ASSERT_TRUE(level_files_.empty()); } TEST(AddBoundaryInputsTest, TestEmptyLevelFiles) { - FileMetaData *f1 = + FileMetaData* f1 = CreateFileMetaData(1, InternalKey("100", 2, kTypeValue), InternalKey(InternalKey("100", 1, kTypeValue))); - compactionFiles_.push_back(f1); + compaction_files_.push_back(f1); - AddBoundaryInputs(icmp_, levelFiles_, &compactionFiles_); - ASSERT_EQ(1, compactionFiles_.size()); - ASSERT_EQ(f1, compactionFiles_[0]); - ASSERT_TRUE(levelFiles_.empty()); + AddBoundaryInputs(icmp_, level_files_, &compaction_files_); + ASSERT_EQ(1, compaction_files_.size()); + ASSERT_EQ(f1, compaction_files_[0]); + ASSERT_TRUE(level_files_.empty()); } TEST(AddBoundaryInputsTest, TestEmptyCompactionFiles) { - FileMetaData *f1 = + FileMetaData* f1 = CreateFileMetaData(1, InternalKey("100", 2, kTypeValue), InternalKey(InternalKey("100", 1, kTypeValue))); - levelFiles_.push_back(f1); + level_files_.push_back(f1); - AddBoundaryInputs(icmp_, levelFiles_, &compactionFiles_); - ASSERT_TRUE(compactionFiles_.empty()); - ASSERT_EQ(1, levelFiles_.size()); - ASSERT_EQ(f1, levelFiles_[0]); + AddBoundaryInputs(icmp_, level_files_, &compaction_files_); + ASSERT_TRUE(compaction_files_.empty()); + ASSERT_EQ(1, level_files_.size()); + ASSERT_EQ(f1, level_files_[0]); } TEST(AddBoundaryInputsTest, TestNoBoundaryFiles) { - FileMetaData *f1 = + FileMetaData* f1 = CreateFileMetaData(1, InternalKey("100", 2, kTypeValue), InternalKey(InternalKey("100", 1, kTypeValue))); - FileMetaData *f2 = + FileMetaData* f2 = CreateFileMetaData(1, InternalKey("200", 2, kTypeValue), InternalKey(InternalKey("200", 1, kTypeValue))); - FileMetaData *f3 = + FileMetaData* f3 = CreateFileMetaData(1, InternalKey("300", 2, kTypeValue), InternalKey(InternalKey("300", 1, kTypeValue))); - levelFiles_.push_back(f3); - levelFiles_.push_back(f2); - levelFiles_.push_back(f1); - compactionFiles_.push_back(f2); - compactionFiles_.push_back(f3); + level_files_.push_back(f3); + level_files_.push_back(f2); + level_files_.push_back(f1); + compaction_files_.push_back(f2); + compaction_files_.push_back(f3); - AddBoundaryInputs(icmp_, levelFiles_, &compactionFiles_); - ASSERT_EQ(2, compactionFiles_.size()); + AddBoundaryInputs(icmp_, level_files_, &compaction_files_); + ASSERT_EQ(2, compaction_files_.size()); } TEST(AddBoundaryInputsTest, TestOneBoundaryFiles) { - FileMetaData *f1 = + FileMetaData* f1 = CreateFileMetaData(1, InternalKey("100", 3, kTypeValue), InternalKey(InternalKey("100", 2, kTypeValue))); - FileMetaData *f2 = + FileMetaData* f2 = CreateFileMetaData(1, InternalKey("100", 1, kTypeValue), InternalKey(InternalKey("200", 3, kTypeValue))); - FileMetaData *f3 = + FileMetaData* f3 = CreateFileMetaData(1, InternalKey("300", 2, kTypeValue), InternalKey(InternalKey("300", 1, kTypeValue))); - levelFiles_.push_back(f3); - levelFiles_.push_back(f2); - levelFiles_.push_back(f1); - compactionFiles_.push_back(f1); + level_files_.push_back(f3); + level_files_.push_back(f2); + level_files_.push_back(f1); + compaction_files_.push_back(f1); - AddBoundaryInputs(icmp_, levelFiles_, &compactionFiles_); - ASSERT_EQ(2, compactionFiles_.size()); - ASSERT_EQ(f1, compactionFiles_[0]); - ASSERT_EQ(f2, compactionFiles_[1]); + AddBoundaryInputs(icmp_, level_files_, &compaction_files_); + ASSERT_EQ(2, compaction_files_.size()); + ASSERT_EQ(f1, compaction_files_[0]); + ASSERT_EQ(f2, compaction_files_[1]); } TEST(AddBoundaryInputsTest, TestTwoBoundaryFiles) { - FileMetaData *f1 = + FileMetaData* f1 = CreateFileMetaData(1, InternalKey("100", 6, kTypeValue), InternalKey(InternalKey("100", 5, kTypeValue))); - FileMetaData *f2 = + FileMetaData* f2 = CreateFileMetaData(1, InternalKey("100", 2, kTypeValue), InternalKey(InternalKey("300", 1, kTypeValue))); - FileMetaData *f3 = + FileMetaData* f3 = CreateFileMetaData(1, InternalKey("100", 4, kTypeValue), InternalKey(InternalKey("100", 3, kTypeValue))); - levelFiles_.push_back(f2); - levelFiles_.push_back(f3); - levelFiles_.push_back(f1); - compactionFiles_.push_back(f1); + level_files_.push_back(f2); + level_files_.push_back(f3); + level_files_.push_back(f1); + compaction_files_.push_back(f1); - AddBoundaryInputs(icmp_, levelFiles_, &compactionFiles_); - ASSERT_EQ(3, compactionFiles_.size()); - ASSERT_EQ(f1, compactionFiles_[0]); - ASSERT_EQ(f3, compactionFiles_[1]); - ASSERT_EQ(f2, compactionFiles_[2]); + AddBoundaryInputs(icmp_, level_files_, &compaction_files_); + ASSERT_EQ(3, compaction_files_.size()); + ASSERT_EQ(f1, compaction_files_[0]); + ASSERT_EQ(f3, compaction_files_[1]); + ASSERT_EQ(f2, compaction_files_[2]); } TEST(AddBoundaryInputsTest, TestDisjoinFilePointers) { - FileMetaData *f1 = CreateFileMetaData(1, InternalKey("100", 6, kTypeValue), InternalKey(InternalKey("100", 5, kTypeValue))); - FileMetaData *f2 = CreateFileMetaData(1, InternalKey("100", 6, kTypeValue), InternalKey(InternalKey("100", 5, kTypeValue))); - FileMetaData *f3 = CreateFileMetaData(1, InternalKey("100", 2, kTypeValue), InternalKey(InternalKey("300", 1, kTypeValue))); - FileMetaData *f4 = CreateFileMetaData(1, InternalKey("100", 4, kTypeValue), InternalKey(InternalKey("100", 3, kTypeValue))); - - levelFiles_.push_back(f2); - levelFiles_.push_back(f3); - levelFiles_.push_back(f4); - - compactionFiles_.push_back(f1); - - AddBoundaryInputs(icmp_, levelFiles_, &compactionFiles_); - ASSERT_EQ(3, compactionFiles_.size()); - ASSERT_EQ(f1, compactionFiles_[0]); - ASSERT_EQ(f4, compactionFiles_[1]); - ASSERT_EQ(f3, compactionFiles_[2]); -} + FileMetaData* f1 = + CreateFileMetaData(1, InternalKey("100", 6, kTypeValue), + InternalKey(InternalKey("100", 5, kTypeValue))); + FileMetaData* f2 = + CreateFileMetaData(1, InternalKey("100", 6, kTypeValue), + InternalKey(InternalKey("100", 5, kTypeValue))); + FileMetaData* f3 = + CreateFileMetaData(1, InternalKey("100", 2, kTypeValue), + InternalKey(InternalKey("300", 1, kTypeValue))); + FileMetaData* f4 = + CreateFileMetaData(1, InternalKey("100", 4, kTypeValue), + InternalKey(InternalKey("100", 3, kTypeValue))); -} // namespace leveldb + level_files_.push_back(f2); + level_files_.push_back(f3); + level_files_.push_back(f4); -int main(int argc, char** argv) { - return leveldb::test::RunAllTests(); + compaction_files_.push_back(f1); + + AddBoundaryInputs(icmp_, level_files_, &compaction_files_); + ASSERT_EQ(3, compaction_files_.size()); + ASSERT_EQ(f1, compaction_files_[0]); + ASSERT_EQ(f4, compaction_files_[1]); + ASSERT_EQ(f3, compaction_files_[2]); } + +} // namespace leveldb + +int main(int argc, char** argv) { return leveldb::test::RunAllTests(); } |