summaryrefslogtreecommitdiffstats
path: root/src/rocksdb/db/file_indexer_test.cc
diff options
context:
space:
mode:
Diffstat (limited to 'src/rocksdb/db/file_indexer_test.cc')
-rw-r--r--src/rocksdb/db/file_indexer_test.cc350
1 files changed, 350 insertions, 0 deletions
diff --git a/src/rocksdb/db/file_indexer_test.cc b/src/rocksdb/db/file_indexer_test.cc
new file mode 100644
index 00000000..935a01ef
--- /dev/null
+++ b/src/rocksdb/db/file_indexer_test.cc
@@ -0,0 +1,350 @@
+// Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
+// This source code is licensed under both the GPLv2 (found in the
+// COPYING file in the root directory) and Apache 2.0 License
+// (found in the LICENSE.Apache file in the root directory).
+//
+// 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 <string>
+#include "db/file_indexer.h"
+#include "db/dbformat.h"
+#include "db/version_edit.h"
+#include "port/stack_trace.h"
+#include "rocksdb/comparator.h"
+#include "util/testharness.h"
+#include "util/testutil.h"
+
+namespace rocksdb {
+
+class IntComparator : public Comparator {
+ public:
+ int Compare(const Slice& a, const Slice& b) const override {
+ assert(a.size() == 8);
+ assert(b.size() == 8);
+ int64_t diff = *reinterpret_cast<const int64_t*>(a.data()) -
+ *reinterpret_cast<const int64_t*>(b.data());
+ if (diff < 0) {
+ return -1;
+ } else if (diff == 0) {
+ return 0;
+ } else {
+ return 1;
+ }
+ }
+
+ const char* Name() const override { return "IntComparator"; }
+
+ void FindShortestSeparator(std::string* /*start*/,
+ const Slice& /*limit*/) const override {}
+
+ void FindShortSuccessor(std::string* /*key*/) const override {}
+};
+
+class FileIndexerTest : public testing::Test {
+ public:
+ FileIndexerTest()
+ : kNumLevels(4), files(new std::vector<FileMetaData*>[kNumLevels]) {}
+
+ ~FileIndexerTest() override {
+ ClearFiles();
+ delete[] files;
+ }
+
+ void AddFile(int level, int64_t smallest, int64_t largest) {
+ auto* f = new FileMetaData();
+ f->smallest = IntKey(smallest);
+ f->largest = IntKey(largest);
+ files[level].push_back(f);
+ }
+
+ InternalKey IntKey(int64_t v) {
+ return InternalKey(Slice(reinterpret_cast<char*>(&v), 8), 0, kTypeValue);
+ }
+
+ void ClearFiles() {
+ for (uint32_t i = 0; i < kNumLevels; ++i) {
+ for (auto* f : files[i]) {
+ delete f;
+ }
+ files[i].clear();
+ }
+ }
+
+ void GetNextLevelIndex(const uint32_t level, const uint32_t file_index,
+ const int cmp_smallest, const int cmp_largest, int32_t* left_index,
+ int32_t* right_index) {
+ *left_index = 100;
+ *right_index = 100;
+ indexer->GetNextLevelIndex(level, file_index, cmp_smallest, cmp_largest,
+ left_index, right_index);
+ }
+
+ int32_t left = 100;
+ int32_t right = 100;
+ const uint32_t kNumLevels;
+ IntComparator ucmp;
+ FileIndexer* indexer;
+
+ std::vector<FileMetaData*>* files;
+};
+
+// Case 0: Empty
+TEST_F(FileIndexerTest, Empty) {
+ Arena arena;
+ indexer = new FileIndexer(&ucmp);
+ indexer->UpdateIndex(&arena, 0, files);
+ delete indexer;
+}
+
+// Case 1: no overlap, files are on the left of next level files
+TEST_F(FileIndexerTest, no_overlap_left) {
+ Arena arena;
+ indexer = new FileIndexer(&ucmp);
+ // level 1
+ AddFile(1, 100, 200);
+ AddFile(1, 300, 400);
+ AddFile(1, 500, 600);
+ // level 2
+ AddFile(2, 1500, 1600);
+ AddFile(2, 1601, 1699);
+ AddFile(2, 1700, 1800);
+ // level 3
+ AddFile(3, 2500, 2600);
+ AddFile(3, 2601, 2699);
+ AddFile(3, 2700, 2800);
+ indexer->UpdateIndex(&arena, kNumLevels, files);
+ for (uint32_t level = 1; level < 3; ++level) {
+ for (uint32_t f = 0; f < 3; ++f) {
+ GetNextLevelIndex(level, f, -1, -1, &left, &right);
+ ASSERT_EQ(0, left);
+ ASSERT_EQ(-1, right);
+ GetNextLevelIndex(level, f, 0, -1, &left, &right);
+ ASSERT_EQ(0, left);
+ ASSERT_EQ(-1, right);
+ GetNextLevelIndex(level, f, 1, -1, &left, &right);
+ ASSERT_EQ(0, left);
+ ASSERT_EQ(-1, right);
+ GetNextLevelIndex(level, f, 1, 0, &left, &right);
+ ASSERT_EQ(0, left);
+ ASSERT_EQ(-1, right);
+ GetNextLevelIndex(level, f, 1, 1, &left, &right);
+ ASSERT_EQ(0, left);
+ ASSERT_EQ(2, right);
+ }
+ }
+ delete indexer;
+ ClearFiles();
+}
+
+// Case 2: no overlap, files are on the right of next level files
+TEST_F(FileIndexerTest, no_overlap_right) {
+ Arena arena;
+ indexer = new FileIndexer(&ucmp);
+ // level 1
+ AddFile(1, 2100, 2200);
+ AddFile(1, 2300, 2400);
+ AddFile(1, 2500, 2600);
+ // level 2
+ AddFile(2, 1500, 1600);
+ AddFile(2, 1501, 1699);
+ AddFile(2, 1700, 1800);
+ // level 3
+ AddFile(3, 500, 600);
+ AddFile(3, 501, 699);
+ AddFile(3, 700, 800);
+ indexer->UpdateIndex(&arena, kNumLevels, files);
+ for (uint32_t level = 1; level < 3; ++level) {
+ for (uint32_t f = 0; f < 3; ++f) {
+ GetNextLevelIndex(level, f, -1, -1, &left, &right);
+ ASSERT_EQ(f == 0 ? 0 : 3, left);
+ ASSERT_EQ(2, right);
+ GetNextLevelIndex(level, f, 0, -1, &left, &right);
+ ASSERT_EQ(3, left);
+ ASSERT_EQ(2, right);
+ GetNextLevelIndex(level, f, 1, -1, &left, &right);
+ ASSERT_EQ(3, left);
+ ASSERT_EQ(2, right);
+ GetNextLevelIndex(level, f, 1, -1, &left, &right);
+ ASSERT_EQ(3, left);
+ ASSERT_EQ(2, right);
+ GetNextLevelIndex(level, f, 1, 0, &left, &right);
+ ASSERT_EQ(3, left);
+ ASSERT_EQ(2, right);
+ GetNextLevelIndex(level, f, 1, 1, &left, &right);
+ ASSERT_EQ(3, left);
+ ASSERT_EQ(2, right);
+ }
+ }
+ delete indexer;
+}
+
+// Case 3: empty L2
+TEST_F(FileIndexerTest, empty_L2) {
+ Arena arena;
+ indexer = new FileIndexer(&ucmp);
+ for (uint32_t i = 1; i < kNumLevels; ++i) {
+ ASSERT_EQ(0U, indexer->LevelIndexSize(i));
+ }
+ // level 1
+ AddFile(1, 2100, 2200);
+ AddFile(1, 2300, 2400);
+ AddFile(1, 2500, 2600);
+ // level 3
+ AddFile(3, 500, 600);
+ AddFile(3, 501, 699);
+ AddFile(3, 700, 800);
+ indexer->UpdateIndex(&arena, kNumLevels, files);
+ for (uint32_t f = 0; f < 3; ++f) {
+ GetNextLevelIndex(1, f, -1, -1, &left, &right);
+ ASSERT_EQ(0, left);
+ ASSERT_EQ(-1, right);
+ GetNextLevelIndex(1, f, 0, -1, &left, &right);
+ ASSERT_EQ(0, left);
+ ASSERT_EQ(-1, right);
+ GetNextLevelIndex(1, f, 1, -1, &left, &right);
+ ASSERT_EQ(0, left);
+ ASSERT_EQ(-1, right);
+ GetNextLevelIndex(1, f, 1, -1, &left, &right);
+ ASSERT_EQ(0, left);
+ ASSERT_EQ(-1, right);
+ GetNextLevelIndex(1, f, 1, 0, &left, &right);
+ ASSERT_EQ(0, left);
+ ASSERT_EQ(-1, right);
+ GetNextLevelIndex(1, f, 1, 1, &left, &right);
+ ASSERT_EQ(0, left);
+ ASSERT_EQ(-1, right);
+ }
+ delete indexer;
+ ClearFiles();
+}
+
+// Case 4: mixed
+TEST_F(FileIndexerTest, mixed) {
+ Arena arena;
+ indexer = new FileIndexer(&ucmp);
+ // level 1
+ AddFile(1, 100, 200);
+ AddFile(1, 250, 400);
+ AddFile(1, 450, 500);
+ // level 2
+ AddFile(2, 100, 150); // 0
+ AddFile(2, 200, 250); // 1
+ AddFile(2, 251, 300); // 2
+ AddFile(2, 301, 350); // 3
+ AddFile(2, 500, 600); // 4
+ // level 3
+ AddFile(3, 0, 50);
+ AddFile(3, 100, 200);
+ AddFile(3, 201, 250);
+ indexer->UpdateIndex(&arena, kNumLevels, files);
+ // level 1, 0
+ GetNextLevelIndex(1, 0, -1, -1, &left, &right);
+ ASSERT_EQ(0, left);
+ ASSERT_EQ(0, right);
+ GetNextLevelIndex(1, 0, 0, -1, &left, &right);
+ ASSERT_EQ(0, left);
+ ASSERT_EQ(0, right);
+ GetNextLevelIndex(1, 0, 1, -1, &left, &right);
+ ASSERT_EQ(0, left);
+ ASSERT_EQ(1, right);
+ GetNextLevelIndex(1, 0, 1, 0, &left, &right);
+ ASSERT_EQ(1, left);
+ ASSERT_EQ(1, right);
+ GetNextLevelIndex(1, 0, 1, 1, &left, &right);
+ ASSERT_EQ(1, left);
+ ASSERT_EQ(4, right);
+ // level 1, 1
+ GetNextLevelIndex(1, 1, -1, -1, &left, &right);
+ ASSERT_EQ(1, left);
+ ASSERT_EQ(1, right);
+ GetNextLevelIndex(1, 1, 0, -1, &left, &right);
+ ASSERT_EQ(1, left);
+ ASSERT_EQ(1, right);
+ GetNextLevelIndex(1, 1, 1, -1, &left, &right);
+ ASSERT_EQ(1, left);
+ ASSERT_EQ(3, right);
+ GetNextLevelIndex(1, 1, 1, 0, &left, &right);
+ ASSERT_EQ(4, left);
+ ASSERT_EQ(3, right);
+ GetNextLevelIndex(1, 1, 1, 1, &left, &right);
+ ASSERT_EQ(4, left);
+ ASSERT_EQ(4, right);
+ // level 1, 2
+ GetNextLevelIndex(1, 2, -1, -1, &left, &right);
+ ASSERT_EQ(4, left);
+ ASSERT_EQ(3, right);
+ GetNextLevelIndex(1, 2, 0, -1, &left, &right);
+ ASSERT_EQ(4, left);
+ ASSERT_EQ(3, right);
+ GetNextLevelIndex(1, 2, 1, -1, &left, &right);
+ ASSERT_EQ(4, left);
+ ASSERT_EQ(4, right);
+ GetNextLevelIndex(1, 2, 1, 0, &left, &right);
+ ASSERT_EQ(4, left);
+ ASSERT_EQ(4, right);
+ GetNextLevelIndex(1, 2, 1, 1, &left, &right);
+ ASSERT_EQ(4, left);
+ ASSERT_EQ(4, right);
+ // level 2, 0
+ GetNextLevelIndex(2, 0, -1, -1, &left, &right);
+ ASSERT_EQ(0, left);
+ ASSERT_EQ(1, right);
+ GetNextLevelIndex(2, 0, 0, -1, &left, &right);
+ ASSERT_EQ(1, left);
+ ASSERT_EQ(1, right);
+ GetNextLevelIndex(2, 0, 1, -1, &left, &right);
+ ASSERT_EQ(1, left);
+ ASSERT_EQ(1, right);
+ GetNextLevelIndex(2, 0, 1, 0, &left, &right);
+ ASSERT_EQ(1, left);
+ ASSERT_EQ(1, right);
+ GetNextLevelIndex(2, 0, 1, 1, &left, &right);
+ ASSERT_EQ(1, left);
+ ASSERT_EQ(2, right);
+ // level 2, 1
+ GetNextLevelIndex(2, 1, -1, -1, &left, &right);
+ ASSERT_EQ(1, left);
+ ASSERT_EQ(1, right);
+ GetNextLevelIndex(2, 1, 0, -1, &left, &right);
+ ASSERT_EQ(1, left);
+ ASSERT_EQ(1, right);
+ GetNextLevelIndex(2, 1, 1, -1, &left, &right);
+ ASSERT_EQ(1, left);
+ ASSERT_EQ(2, right);
+ GetNextLevelIndex(2, 1, 1, 0, &left, &right);
+ ASSERT_EQ(2, left);
+ ASSERT_EQ(2, right);
+ GetNextLevelIndex(2, 1, 1, 1, &left, &right);
+ ASSERT_EQ(2, left);
+ ASSERT_EQ(2, right);
+ // level 2, [2 - 4], no overlap
+ for (uint32_t f = 2; f <= 4; ++f) {
+ GetNextLevelIndex(2, f, -1, -1, &left, &right);
+ ASSERT_EQ(f == 2 ? 2 : 3, left);
+ ASSERT_EQ(2, right);
+ GetNextLevelIndex(2, f, 0, -1, &left, &right);
+ ASSERT_EQ(3, left);
+ ASSERT_EQ(2, right);
+ GetNextLevelIndex(2, f, 1, -1, &left, &right);
+ ASSERT_EQ(3, left);
+ ASSERT_EQ(2, right);
+ GetNextLevelIndex(2, f, 1, 0, &left, &right);
+ ASSERT_EQ(3, left);
+ ASSERT_EQ(2, right);
+ GetNextLevelIndex(2, f, 1, 1, &left, &right);
+ ASSERT_EQ(3, left);
+ ASSERT_EQ(2, right);
+ }
+ delete indexer;
+ ClearFiles();
+}
+
+} // namespace rocksdb
+
+int main(int argc, char** argv) {
+ rocksdb::port::InstallStackTraceHandler();
+ ::testing::InitGoogleTest(&argc, argv);
+ return RUN_ALL_TESTS();
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-05 01:26:44 +0000