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