1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
2 // This source code is licensed under both the GPLv2 (found in the
3 // COPYING file in the root directory) and Apache 2.0 License
4 // (found in the LICENSE.Apache file in the root directory).
5 //
6 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
7 // Use of this source code is governed by a BSD-style license that can be
8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
9
10 #include "db/file_indexer.h"
11 #include <algorithm>
12 #include <functional>
13 #include "db/version_edit.h"
14 #include "rocksdb/comparator.h"
15
16 namespace ROCKSDB_NAMESPACE {
17
FileIndexer(const Comparator * ucmp)18 FileIndexer::FileIndexer(const Comparator* ucmp)
19 : num_levels_(0), ucmp_(ucmp), level_rb_(nullptr) {}
20
NumLevelIndex() const21 size_t FileIndexer::NumLevelIndex() const { return next_level_index_.size(); }
22
LevelIndexSize(size_t level) const23 size_t FileIndexer::LevelIndexSize(size_t level) const {
24 if (level >= next_level_index_.size()) {
25 return 0;
26 }
27 return next_level_index_[level].num_index;
28 }
29
GetNextLevelIndex(const size_t level,const size_t file_index,const int cmp_smallest,const int cmp_largest,int32_t * left_bound,int32_t * right_bound) const30 void FileIndexer::GetNextLevelIndex(const size_t level, const size_t file_index,
31 const int cmp_smallest,
32 const int cmp_largest, int32_t* left_bound,
33 int32_t* right_bound) const {
34 assert(level > 0);
35
36 // Last level, no hint
37 if (level == num_levels_ - 1) {
38 *left_bound = 0;
39 *right_bound = -1;
40 return;
41 }
42
43 assert(level < num_levels_ - 1);
44 assert(static_cast<int32_t>(file_index) <= level_rb_[level]);
45
46 const IndexUnit* index_units = next_level_index_[level].index_units;
47 const auto& index = index_units[file_index];
48
49 if (cmp_smallest < 0) {
50 *left_bound = (level > 0 && file_index > 0)
51 ? index_units[file_index - 1].largest_lb
52 : 0;
53 *right_bound = index.smallest_rb;
54 } else if (cmp_smallest == 0) {
55 *left_bound = index.smallest_lb;
56 *right_bound = index.smallest_rb;
57 } else if (cmp_smallest > 0 && cmp_largest < 0) {
58 *left_bound = index.smallest_lb;
59 *right_bound = index.largest_rb;
60 } else if (cmp_largest == 0) {
61 *left_bound = index.largest_lb;
62 *right_bound = index.largest_rb;
63 } else if (cmp_largest > 0) {
64 *left_bound = index.largest_lb;
65 *right_bound = level_rb_[level + 1];
66 } else {
67 assert(false);
68 }
69
70 assert(*left_bound >= 0);
71 assert(*left_bound <= *right_bound + 1);
72 assert(*right_bound <= level_rb_[level + 1]);
73 }
74
UpdateIndex(Arena * arena,const size_t num_levels,std::vector<FileMetaData * > * const files)75 void FileIndexer::UpdateIndex(Arena* arena, const size_t num_levels,
76 std::vector<FileMetaData*>* const files) {
77 if (files == nullptr) {
78 return;
79 }
80 if (num_levels == 0) { // uint_32 0-1 would cause bad behavior
81 num_levels_ = num_levels;
82 return;
83 }
84 assert(level_rb_ == nullptr); // level_rb_ should be init here
85
86 num_levels_ = num_levels;
87 next_level_index_.resize(num_levels);
88
89 char* mem = arena->AllocateAligned(num_levels_ * sizeof(int32_t));
90 level_rb_ = new (mem) int32_t[num_levels_];
91 for (size_t i = 0; i < num_levels_; i++) {
92 level_rb_[i] = -1;
93 }
94
95 // L1 - Ln-1
96 for (size_t level = 1; level < num_levels_ - 1; ++level) {
97 const auto& upper_files = files[level];
98 const int32_t upper_size = static_cast<int32_t>(upper_files.size());
99 const auto& lower_files = files[level + 1];
100 level_rb_[level] = static_cast<int32_t>(upper_files.size()) - 1;
101 if (upper_size == 0) {
102 continue;
103 }
104 IndexLevel& index_level = next_level_index_[level];
105 index_level.num_index = upper_size;
106 mem = arena->AllocateAligned(upper_size * sizeof(IndexUnit));
107 index_level.index_units = new (mem) IndexUnit[upper_size];
108
109 CalculateLB(
110 upper_files, lower_files, &index_level,
111 [this](const FileMetaData* a, const FileMetaData* b) -> int {
112 return ucmp_->CompareWithoutTimestamp(a->smallest.user_key(),
113 b->largest.user_key());
114 },
115 [](IndexUnit* index, int32_t f_idx) { index->smallest_lb = f_idx; });
116 CalculateLB(
117 upper_files, lower_files, &index_level,
118 [this](const FileMetaData* a, const FileMetaData* b) -> int {
119 return ucmp_->CompareWithoutTimestamp(a->largest.user_key(),
120 b->largest.user_key());
121 },
122 [](IndexUnit* index, int32_t f_idx) { index->largest_lb = f_idx; });
123 CalculateRB(
124 upper_files, lower_files, &index_level,
125 [this](const FileMetaData* a, const FileMetaData* b) -> int {
126 return ucmp_->CompareWithoutTimestamp(a->smallest.user_key(),
127 b->smallest.user_key());
128 },
129 [](IndexUnit* index, int32_t f_idx) { index->smallest_rb = f_idx; });
130 CalculateRB(
131 upper_files, lower_files, &index_level,
132 [this](const FileMetaData* a, const FileMetaData* b) -> int {
133 return ucmp_->CompareWithoutTimestamp(a->largest.user_key(),
134 b->smallest.user_key());
135 },
136 [](IndexUnit* index, int32_t f_idx) { index->largest_rb = f_idx; });
137 }
138
139 level_rb_[num_levels_ - 1] =
140 static_cast<int32_t>(files[num_levels_ - 1].size()) - 1;
141 }
142
CalculateLB(const std::vector<FileMetaData * > & upper_files,const std::vector<FileMetaData * > & lower_files,IndexLevel * index_level,std::function<int (const FileMetaData *,const FileMetaData *)> cmp_op,std::function<void (IndexUnit *,int32_t)> set_index)143 void FileIndexer::CalculateLB(
144 const std::vector<FileMetaData*>& upper_files,
145 const std::vector<FileMetaData*>& lower_files, IndexLevel* index_level,
146 std::function<int(const FileMetaData*, const FileMetaData*)> cmp_op,
147 std::function<void(IndexUnit*, int32_t)> set_index) {
148 const int32_t upper_size = static_cast<int32_t>(upper_files.size());
149 const int32_t lower_size = static_cast<int32_t>(lower_files.size());
150 int32_t upper_idx = 0;
151 int32_t lower_idx = 0;
152
153 IndexUnit* index = index_level->index_units;
154 while (upper_idx < upper_size && lower_idx < lower_size) {
155 int cmp = cmp_op(upper_files[upper_idx], lower_files[lower_idx]);
156
157 if (cmp == 0) {
158 set_index(&index[upper_idx], lower_idx);
159 ++upper_idx;
160 } else if (cmp > 0) {
161 // Lower level's file (largest) is smaller, a key won't hit in that
162 // file. Move to next lower file
163 ++lower_idx;
164 } else {
165 // Lower level's file becomes larger, update the index, and
166 // move to the next upper file
167 set_index(&index[upper_idx], lower_idx);
168 ++upper_idx;
169 }
170 }
171
172 while (upper_idx < upper_size) {
173 // Lower files are exhausted, that means the remaining upper files are
174 // greater than any lower files. Set the index to be the lower level size.
175 set_index(&index[upper_idx], lower_size);
176 ++upper_idx;
177 }
178 }
179
CalculateRB(const std::vector<FileMetaData * > & upper_files,const std::vector<FileMetaData * > & lower_files,IndexLevel * index_level,std::function<int (const FileMetaData *,const FileMetaData *)> cmp_op,std::function<void (IndexUnit *,int32_t)> set_index)180 void FileIndexer::CalculateRB(
181 const std::vector<FileMetaData*>& upper_files,
182 const std::vector<FileMetaData*>& lower_files, IndexLevel* index_level,
183 std::function<int(const FileMetaData*, const FileMetaData*)> cmp_op,
184 std::function<void(IndexUnit*, int32_t)> set_index) {
185 const int32_t upper_size = static_cast<int32_t>(upper_files.size());
186 const int32_t lower_size = static_cast<int32_t>(lower_files.size());
187 int32_t upper_idx = upper_size - 1;
188 int32_t lower_idx = lower_size - 1;
189
190 IndexUnit* index = index_level->index_units;
191 while (upper_idx >= 0 && lower_idx >= 0) {
192 int cmp = cmp_op(upper_files[upper_idx], lower_files[lower_idx]);
193
194 if (cmp == 0) {
195 set_index(&index[upper_idx], lower_idx);
196 --upper_idx;
197 } else if (cmp < 0) {
198 // Lower level's file (smallest) is larger, a key won't hit in that
199 // file. Move to next lower file.
200 --lower_idx;
201 } else {
202 // Lower level's file becomes smaller, update the index, and move to
203 // the next the upper file
204 set_index(&index[upper_idx], lower_idx);
205 --upper_idx;
206 }
207 }
208 while (upper_idx >= 0) {
209 // Lower files are exhausted, that means the remaining upper files are
210 // smaller than any lower files. Set it to -1.
211 set_index(&index[upper_idx], -1);
212 --upper_idx;
213 }
214 }
215
216 } // namespace ROCKSDB_NAMESPACE
217