Branch data Line data Source code
1 : : // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
2 : : // Use of this source code is governed by a BSD-style license that can be
3 : : // found in the LICENSE file. See the AUTHORS file for names of contributors.
4 : : //
5 : : // Decodes the blocks generated by block_builder.cc.
6 : :
7 : : #include "table/block.h"
8 : :
9 : : #include <algorithm>
10 : : #include <cstdint>
11 : : #include <vector>
12 : :
13 : : #include "leveldb/comparator.h"
14 : : #include "table/format.h"
15 : : #include "util/coding.h"
16 : : #include "util/logging.h"
17 : :
18 : : namespace leveldb {
19 : :
20 : 1360107 : inline uint32_t Block::NumRestarts() const {
21 [ - + ]: 1360107 : assert(size_ >= sizeof(uint32_t));
22 : 1360107 : return DecodeFixed32(data_ + size_ - sizeof(uint32_t));
23 : : }
24 : :
25 : 2054 : Block::Block(const BlockContents& contents)
26 [ - + ]: 2054 : : data_(contents.data.data()),
27 [ - + ]: 2054 : size_(contents.data.size()),
28 : 2054 : owned_(contents.heap_allocated) {
29 [ - + ]: 2054 : if (size_ < sizeof(uint32_t)) {
30 : 0 : size_ = 0; // Error marker
31 : : } else {
32 : 2054 : size_t max_restarts_allowed = (size_ - sizeof(uint32_t)) / sizeof(uint32_t);
33 [ - + ]: 2054 : if (NumRestarts() > max_restarts_allowed) {
34 : : // The size is too small for NumRestarts()
35 : 0 : size_ = 0;
36 : : } else {
37 : 2054 : restart_offset_ = size_ - (1 + NumRestarts()) * sizeof(uint32_t);
38 : : }
39 : : }
40 : 2054 : }
41 : :
42 : 2054 : Block::~Block() {
43 [ + + ]: 2054 : if (owned_) {
44 [ + - ]: 257 : delete[] data_;
45 : : }
46 : 2054 : }
47 : :
48 : : // Helper routine: decode the next block entry starting at "p",
49 : : // storing the number of shared key bytes, non_shared key bytes,
50 : : // and the length of the value in "*shared", "*non_shared", and
51 : : // "*value_length", respectively. Will not dereference past "limit".
52 : : //
53 : : // If any errors are detected, returns nullptr. Otherwise, returns a
54 : : // pointer to the key delta (just past the three decoded values).
55 : 13651628 : static inline const char* DecodeEntry(const char* p, const char* limit,
56 : : uint32_t* shared, uint32_t* non_shared,
57 : : uint32_t* value_length) {
58 [ + - ]: 13651628 : if (limit - p < 3) return nullptr;
59 : 13651628 : *shared = reinterpret_cast<const uint8_t*>(p)[0];
60 : 13651628 : *non_shared = reinterpret_cast<const uint8_t*>(p)[1];
61 : 13651628 : *value_length = reinterpret_cast<const uint8_t*>(p)[2];
62 [ + + ]: 13651628 : if ((*shared | *non_shared | *value_length) < 128) {
63 : : // Fast path: all three values are encoded in one byte each
64 : 13651607 : p += 3;
65 : : } else {
66 [ + - ]: 21 : if ((p = GetVarint32Ptr(p, limit, shared)) == nullptr) return nullptr;
67 [ + - ]: 21 : if ((p = GetVarint32Ptr(p, limit, non_shared)) == nullptr) return nullptr;
68 [ + - ]: 21 : if ((p = GetVarint32Ptr(p, limit, value_length)) == nullptr) return nullptr;
69 : : }
70 : :
71 [ - + ]: 13651628 : if (static_cast<uint32_t>(limit - p) < (*non_shared + *value_length)) {
72 : 0 : return nullptr;
73 : : }
74 : : return p;
75 : : }
76 : :
77 : : class Block::Iter : public Iterator {
78 : : private:
79 : : const Comparator* const comparator_;
80 : : const char* const data_; // underlying block contents
81 : : uint32_t const restarts_; // Offset of restart array (list of fixed32)
82 : : uint32_t const num_restarts_; // Number of uint32_t entries in restart array
83 : :
84 : : // current_ is offset in data_ of current entry. >= restarts_ if !Valid
85 : : uint32_t current_;
86 : : uint32_t restart_index_; // Index of restart block in which current_ falls
87 : : std::string key_;
88 : : Slice value_;
89 : : Status status_;
90 : :
91 : 13642168 : inline int Compare(const Slice& a, const Slice& b) const {
92 : 13642168 : return comparator_->Compare(a, b);
93 : : }
94 : :
95 : : // Return the offset in data_ just past the end of the current entry.
96 : 3185747 : inline uint32_t NextEntryOffset() const {
97 [ # # # # ]: 0 : return (value_.data() + value_.size()) - data_;
98 : : }
99 : :
100 : 14965847 : uint32_t GetRestartPoint(uint32_t index) {
101 [ - + ]: 14965847 : assert(index < num_restarts_);
102 : 14965847 : return DecodeFixed32(data_ + restarts_ + index * sizeof(uint32_t));
103 : : }
104 : :
105 : 1357870 : void SeekToRestartPoint(uint32_t index) {
106 : 1357870 : key_.clear();
107 : 1357870 : restart_index_ = index;
108 : : // current_ will be fixed by ParseNextKey();
109 : :
110 : : // ParseNextKey() starts at the end of value_, so set value_ accordingly
111 : 1357870 : uint32_t offset = GetRestartPoint(index);
112 : 1357870 : value_ = Slice(data_ + offset, 0);
113 : 1357870 : }
114 : :
115 : : public:
116 : 1358053 : Iter(const Comparator* comparator, const char* data, uint32_t restarts,
117 : : uint32_t num_restarts)
118 : 2716106 : : comparator_(comparator),
119 : 1358053 : data_(data),
120 : 1358053 : restarts_(restarts),
121 : 1358053 : num_restarts_(num_restarts),
122 : 1358053 : current_(restarts_),
123 [ - + ]: 1358053 : restart_index_(num_restarts_) {
124 [ - + ]: 1358053 : assert(num_restarts_ > 0);
125 : 1358053 : }
126 : :
127 : 2891306 : bool Valid() const override { return current_ < restarts_; }
128 [ - + ]: 1357575 : Status status() const override { return status_; }
129 : 74697 : Slice key() const override {
130 [ - + ]: 74697 : assert(Valid());
131 [ - + ]: 74697 : return key_;
132 : : }
133 : 1438610 : Slice value() const override {
134 [ - + ]: 1438610 : assert(Valid());
135 : 1438610 : return value_;
136 : : }
137 : :
138 : 9692 : void Next() override {
139 [ - + ]: 9692 : assert(Valid());
140 : 9692 : ParseNextKey();
141 : 9692 : }
142 : :
143 : 0 : void Prev() override {
144 [ # # ]: 0 : assert(Valid());
145 : :
146 : : // Scan backwards to a restart point before current_
147 : 0 : const uint32_t original = current_;
148 [ # # ]: 0 : while (GetRestartPoint(restart_index_) >= original) {
149 [ # # ]: 0 : if (restart_index_ == 0) {
150 : : // No more entries
151 : 0 : current_ = restarts_;
152 : 0 : restart_index_ = num_restarts_;
153 : 0 : return;
154 : : }
155 : 0 : restart_index_--;
156 : : }
157 : :
158 : 0 : SeekToRestartPoint(restart_index_);
159 : 0 : do {
160 : : // Loop until end of current entry hits the start of original entry
161 [ # # # # : 0 : } while (ParseNextKey() && NextEntryOffset() < original);
# # ]
162 : : }
163 : :
164 : 1357592 : void Seek(const Slice& target) override {
165 : : // Binary search in restart array to find the last restart point
166 : : // with a key < target
167 : 1357592 : uint32_t left = 0;
168 : 1357592 : uint32_t right = num_restarts_ - 1;
169 [ + + ]: 11824007 : while (left < right) {
170 : 10466415 : uint32_t mid = (left + right + 1) / 2;
171 : 10466415 : uint32_t region_offset = GetRestartPoint(mid);
172 : 10466415 : uint32_t shared, non_shared, value_length;
173 : 10466415 : const char* key_ptr =
174 : 10466415 : DecodeEntry(data_ + region_offset, data_ + restarts_, &shared,
175 : : &non_shared, &value_length);
176 [ + - - + ]: 10466415 : if (key_ptr == nullptr || (shared != 0)) {
177 : 0 : CorruptionError();
178 : 0 : return;
179 : : }
180 : 10466415 : Slice mid_key(key_ptr, non_shared);
181 [ + + ]: 10466415 : if (Compare(mid_key, target) < 0) {
182 : : // Key at "mid" is smaller than "target". Therefore all
183 : : // blocks before "mid" are uninteresting.
184 : : left = mid;
185 : : } else {
186 : : // Key at "mid" is >= "target". Therefore all blocks at or
187 : : // after "mid" are uninteresting.
188 : 4897743 : right = mid - 1;
189 : : }
190 : : }
191 : :
192 : : // Linear search (within restart block) for first key >= target
193 : 1357592 : SeekToRestartPoint(left);
194 : 3175777 : while (true) {
195 [ + + ]: 3175777 : if (!ParseNextKey()) {
196 : : return;
197 : : }
198 [ - + + + ]: 3175753 : if (Compare(key_, target) >= 0) {
199 : : return;
200 : : }
201 : : }
202 : : }
203 : :
204 : 278 : void SeekToFirst() override {
205 : 278 : SeekToRestartPoint(0);
206 : 278 : ParseNextKey();
207 : 278 : }
208 : :
209 : 0 : void SeekToLast() override {
210 : 0 : SeekToRestartPoint(num_restarts_ - 1);
211 [ # # # # : 0 : while (ParseNextKey() && NextEntryOffset() < restarts_) {
# # ]
212 : : // Keep skipping
213 : : }
214 : 0 : }
215 : :
216 : : private:
217 : 0 : void CorruptionError() {
218 : 0 : current_ = restarts_;
219 : 0 : restart_index_ = num_restarts_;
220 [ # # ]: 0 : status_ = Status::Corruption("bad entry in block");
221 : 0 : key_.clear();
222 : 0 : value_.clear();
223 : 0 : }
224 : :
225 : 3185747 : bool ParseNextKey() {
226 [ + + ]: 3185747 : current_ = NextEntryOffset();
227 : 3185747 : const char* p = data_ + current_;
228 : 3185747 : const char* limit = data_ + restarts_; // Restarts come right after data
229 [ + + ]: 3185747 : if (p >= limit) {
230 : : // No more entries to return. Mark as invalid.
231 : 534 : current_ = restarts_;
232 : 534 : restart_index_ = num_restarts_;
233 : 534 : return false;
234 : : }
235 : :
236 : : // Decode next entry
237 : 3185213 : uint32_t shared, non_shared, value_length;
238 : 3185213 : p = DecodeEntry(p, limit, &shared, &non_shared, &value_length);
239 [ + - - + : 3185213 : if (p == nullptr || key_.size() < shared) {
- + ]
240 : 0 : CorruptionError();
241 : 0 : return false;
242 : : } else {
243 : 3185213 : key_.resize(shared);
244 : 3185213 : key_.append(p, non_shared);
245 : 3185213 : value_ = Slice(p + non_shared, value_length);
246 [ + + ]: 3185774 : while (restart_index_ + 1 < num_restarts_ &&
247 [ + + ]: 3141562 : GetRestartPoint(restart_index_ + 1) < current_) {
248 : 561 : ++restart_index_;
249 : : }
250 : : return true;
251 : : }
252 : : }
253 : : };
254 : :
255 : 1358053 : Iterator* Block::NewIterator(const Comparator* comparator) {
256 [ - + ]: 1358053 : if (size_ < sizeof(uint32_t)) {
257 [ # # # # ]: 0 : return NewErrorIterator(Status::Corruption("bad block contents"));
258 : : }
259 : 1358053 : const uint32_t num_restarts = NumRestarts();
260 [ - + ]: 1358053 : if (num_restarts == 0) {
261 : 0 : return NewEmptyIterator();
262 : : } else {
263 [ + - ]: 1358053 : return new Iter(comparator, data_, restart_offset_, num_restarts);
264 : : }
265 : : }
266 : :
267 : : } // namespace leveldb
|
