]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
2 | // This source code is licensed under the BSD-style license found in the | |
3 | // LICENSE file in the root directory of this source tree. An additional grant | |
4 | // of patent rights can be found in the PATENTS file in the same 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 { | |
17 | ||
18 | FileIndexer::FileIndexer(const Comparator* ucmp) | |
19 | : num_levels_(0), ucmp_(ucmp), level_rb_(nullptr) {} | |
20 | ||
21 | size_t FileIndexer::NumLevelIndex() const { return next_level_index_.size(); } | |
22 | ||
23 | 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 | ||
30 | 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 | ||
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_->Compare(a->smallest.user_key(), b->largest.user_key()); | |
113 | }, | |
114 | [](IndexUnit* index, int32_t f_idx) { index->smallest_lb = f_idx; }); | |
115 | CalculateLB( | |
116 | upper_files, lower_files, &index_level, | |
117 | [this](const FileMetaData * a, const FileMetaData * b)->int { | |
118 | return ucmp_->Compare(a->largest.user_key(), b->largest.user_key()); | |
119 | }, | |
120 | [](IndexUnit* index, int32_t f_idx) { index->largest_lb = f_idx; }); | |
121 | CalculateRB( | |
122 | upper_files, lower_files, &index_level, | |
123 | [this](const FileMetaData * a, const FileMetaData * b)->int { | |
124 | return ucmp_->Compare(a->smallest.user_key(), b->smallest.user_key()); | |
125 | }, | |
126 | [](IndexUnit* index, int32_t f_idx) { index->smallest_rb = f_idx; }); | |
127 | CalculateRB( | |
128 | upper_files, lower_files, &index_level, | |
129 | [this](const FileMetaData * a, const FileMetaData * b)->int { | |
130 | return ucmp_->Compare(a->largest.user_key(), b->smallest.user_key()); | |
131 | }, | |
132 | [](IndexUnit* index, int32_t f_idx) { index->largest_rb = f_idx; }); | |
133 | } | |
134 | ||
135 | level_rb_[num_levels_ - 1] = | |
136 | static_cast<int32_t>(files[num_levels_ - 1].size()) - 1; | |
137 | } | |
138 | ||
139 | void FileIndexer::CalculateLB( | |
140 | const std::vector<FileMetaData*>& upper_files, | |
141 | const std::vector<FileMetaData*>& lower_files, IndexLevel* index_level, | |
142 | std::function<int(const FileMetaData*, const FileMetaData*)> cmp_op, | |
143 | std::function<void(IndexUnit*, int32_t)> set_index) { | |
144 | const int32_t upper_size = static_cast<int32_t>(upper_files.size()); | |
145 | const int32_t lower_size = static_cast<int32_t>(lower_files.size()); | |
146 | int32_t upper_idx = 0; | |
147 | int32_t lower_idx = 0; | |
148 | ||
149 | IndexUnit* index = index_level->index_units; | |
150 | while (upper_idx < upper_size && lower_idx < lower_size) { | |
151 | int cmp = cmp_op(upper_files[upper_idx], lower_files[lower_idx]); | |
152 | ||
153 | if (cmp == 0) { | |
154 | set_index(&index[upper_idx], lower_idx); | |
155 | ++upper_idx; | |
156 | ++lower_idx; | |
157 | } else if (cmp > 0) { | |
158 | // Lower level's file (largest) is smaller, a key won't hit in that | |
159 | // file. Move to next lower file | |
160 | ++lower_idx; | |
161 | } else { | |
162 | // Lower level's file becomes larger, update the index, and | |
163 | // move to the next upper file | |
164 | set_index(&index[upper_idx], lower_idx); | |
165 | ++upper_idx; | |
166 | } | |
167 | } | |
168 | ||
169 | while (upper_idx < upper_size) { | |
170 | // Lower files are exhausted, that means the remaining upper files are | |
171 | // greater than any lower files. Set the index to be the lower level size. | |
172 | set_index(&index[upper_idx], lower_size); | |
173 | ++upper_idx; | |
174 | } | |
175 | } | |
176 | ||
177 | void FileIndexer::CalculateRB( | |
178 | const std::vector<FileMetaData*>& upper_files, | |
179 | const std::vector<FileMetaData*>& lower_files, IndexLevel* index_level, | |
180 | std::function<int(const FileMetaData*, const FileMetaData*)> cmp_op, | |
181 | std::function<void(IndexUnit*, int32_t)> set_index) { | |
182 | const int32_t upper_size = static_cast<int32_t>(upper_files.size()); | |
183 | const int32_t lower_size = static_cast<int32_t>(lower_files.size()); | |
184 | int32_t upper_idx = upper_size - 1; | |
185 | int32_t lower_idx = lower_size - 1; | |
186 | ||
187 | IndexUnit* index = index_level->index_units; | |
188 | while (upper_idx >= 0 && lower_idx >= 0) { | |
189 | int cmp = cmp_op(upper_files[upper_idx], lower_files[lower_idx]); | |
190 | ||
191 | if (cmp == 0) { | |
192 | set_index(&index[upper_idx], lower_idx); | |
193 | --upper_idx; | |
194 | --lower_idx; | |
195 | } else if (cmp < 0) { | |
196 | // Lower level's file (smallest) is larger, a key won't hit in that | |
197 | // file. Move to next lower file. | |
198 | --lower_idx; | |
199 | } else { | |
200 | // Lower level's file becomes smaller, update the index, and move to | |
201 | // the next the upper file | |
202 | set_index(&index[upper_idx], lower_idx); | |
203 | --upper_idx; | |
204 | } | |
205 | } | |
206 | while (upper_idx >= 0) { | |
207 | // Lower files are exhausted, that means the remaining upper files are | |
208 | // smaller than any lower files. Set it to -1. | |
209 | set_index(&index[upper_idx], -1); | |
210 | --upper_idx; | |
211 | } | |
212 | } | |
213 | ||
214 | } // namespace rocksdb |