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 : 3544592 : inline uint32_t Block::NumRestarts() const {
# 21 : 3544592 : assert(size_ >= sizeof(uint32_t));
# 22 : 0 : return DecodeFixed32(data_ + size_ - sizeof(uint32_t));
# 23 : 3544592 : }
# 24 : :
# 25 : : Block::Block(const BlockContents& contents)
# 26 : : : data_(contents.data.data()),
# 27 : : size_(contents.data.size()),
# 28 : 25254 : owned_(contents.heap_allocated) {
# 29 [ - + ]: 25254 : if (size_ < sizeof(uint32_t)) {
# 30 : 0 : size_ = 0; // Error marker
# 31 : 25254 : } else {
# 32 : 25254 : size_t max_restarts_allowed = (size_ - sizeof(uint32_t)) / sizeof(uint32_t);
# 33 [ - + ]: 25254 : if (NumRestarts() > max_restarts_allowed) {
# 34 : : // The size is too small for NumRestarts()
# 35 : 0 : size_ = 0;
# 36 : 25254 : } else {
# 37 : 25254 : restart_offset_ = size_ - (1 + NumRestarts()) * sizeof(uint32_t);
# 38 : 25254 : }
# 39 : 25254 : }
# 40 : 25254 : }
# 41 : :
# 42 : 25253 : Block::~Block() {
# 43 [ + + ]: 25253 : if (owned_) {
# 44 : 488 : delete[] data_;
# 45 : 488 : }
# 46 : 25253 : }
# 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 : : static inline const char* DecodeEntry(const char* p, const char* limit,
# 56 : : uint32_t* shared, uint32_t* non_shared,
# 57 : 33935142 : uint32_t* value_length) {
# 58 [ - + ]: 33935142 : if (limit - p < 3) return nullptr;
# 59 : 33935142 : *shared = reinterpret_cast<const uint8_t*>(p)[0];
# 60 : 33935142 : *non_shared = reinterpret_cast<const uint8_t*>(p)[1];
# 61 : 33935142 : *value_length = reinterpret_cast<const uint8_t*>(p)[2];
# 62 [ + + ]: 33935142 : if ((*shared | *non_shared | *value_length) < 128) {
# 63 : : // Fast path: all three values are encoded in one byte each
# 64 : 33934717 : p += 3;
# 65 : 33934717 : } else {
# 66 [ - + ]: 425 : if ((p = GetVarint32Ptr(p, limit, shared)) == nullptr) return nullptr;
# 67 [ - + ]: 425 : if ((p = GetVarint32Ptr(p, limit, non_shared)) == nullptr) return nullptr;
# 68 [ - + ]: 425 : if ((p = GetVarint32Ptr(p, limit, value_length)) == nullptr) return nullptr;
# 69 : 425 : }
# 70 : :
# 71 [ - + ]: 33935142 : if (static_cast<uint32_t>(limit - p) < (*non_shared + *value_length)) {
# 72 : 0 : return nullptr;
# 73 : 0 : }
# 74 : 33935142 : return p;
# 75 : 33935142 : }
# 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 : 33802472 : inline int Compare(const Slice& a, const Slice& b) const {
# 92 : 33802472 : return comparator_->Compare(a, b);
# 93 : 33802472 : }
# 94 : :
# 95 : : // Return the offset in data_ just past the end of the current entry.
# 96 : 7785070 : inline uint32_t NextEntryOffset() const {
# 97 : 7785070 : return (value_.data() + value_.size()) - data_;
# 98 : 7785070 : }
# 99 : :
# 100 : 37309215 : uint32_t GetRestartPoint(uint32_t index) {
# 101 : 37309215 : assert(index < num_restarts_);
# 102 : 0 : return DecodeFixed32(data_ + restarts_ + index * sizeof(uint32_t));
# 103 : 37309215 : }
# 104 : :
# 105 : 3492992 : void SeekToRestartPoint(uint32_t index) {
# 106 : 3492992 : key_.clear();
# 107 : 3492992 : restart_index_ = index;
# 108 : : // current_ will be fixed by ParseNextKey();
# 109 : :
# 110 : : // ParseNextKey() starts at the end of value_, so set value_ accordingly
# 111 : 3492992 : uint32_t offset = GetRestartPoint(index);
# 112 : 3492992 : value_ = Slice(data_ + offset, 0);
# 113 : 3492992 : }
# 114 : :
# 115 : : public:
# 116 : : Iter(const Comparator* comparator, const char* data, uint32_t restarts,
# 117 : : uint32_t num_restarts)
# 118 : : : comparator_(comparator),
# 119 : : data_(data),
# 120 : : restarts_(restarts),
# 121 : : num_restarts_(num_restarts),
# 122 : : current_(restarts_),
# 123 : 3494085 : restart_index_(num_restarts_) {
# 124 : 3494085 : assert(num_restarts_ > 0);
# 125 : 3494085 : }
# 126 : :
# 127 : 7811900 : bool Valid() const override { return current_ < restarts_; }
# 128 : 3489884 : Status status() const override { return status_; }
# 129 : 238003 : Slice key() const override {
# 130 : 238003 : assert(Valid());
# 131 : 0 : return key_;
# 132 : 238003 : }
# 133 : 3807488 : Slice value() const override {
# 134 : 3807488 : assert(Valid());
# 135 : 0 : return value_;
# 136 : 3807488 : }
# 137 : :
# 138 : 133000 : void Next() override {
# 139 : 133000 : assert(Valid());
# 140 : 0 : ParseNextKey();
# 141 : 133000 : }
# 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 : 0 : }
# 155 : 0 : restart_index_--;
# 156 : 0 : }
# 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 : 0 : }
# 163 : :
# 164 : 3488874 : void Seek(const Slice& target) override {
# 165 : : // Binary search in restart array to find the last restart point
# 166 : : // with a key < target
# 167 : 3488874 : uint32_t left = 0;
# 168 : 3488874 : uint32_t right = num_restarts_ - 1;
# 169 [ + + ]: 29644092 : while (left < right) {
# 170 : 26155218 : uint32_t mid = (left + right + 1) / 2;
# 171 : 26155218 : uint32_t region_offset = GetRestartPoint(mid);
# 172 : 26155218 : uint32_t shared, non_shared, value_length;
# 173 : 26155218 : const char* key_ptr =
# 174 : 26155218 : DecodeEntry(data_ + region_offset, data_ + restarts_, &shared,
# 175 : 26155218 : &non_shared, &value_length);
# 176 [ - + ][ - + ]: 26155218 : if (key_ptr == nullptr || (shared != 0)) {
# 177 : 0 : CorruptionError();
# 178 : 0 : return;
# 179 : 0 : }
# 180 : 26155218 : Slice mid_key(key_ptr, non_shared);
# 181 [ + + ]: 26155218 : if (Compare(mid_key, target) < 0) {
# 182 : : // Key at "mid" is smaller than "target". Therefore all
# 183 : : // blocks before "mid" are uninteresting.
# 184 : 14324996 : left = mid;
# 185 : 14324996 : } else {
# 186 : : // Key at "mid" is >= "target". Therefore all blocks at or
# 187 : : // after "mid" are uninteresting.
# 188 : 11830222 : right = mid - 1;
# 189 : 11830222 : }
# 190 : 26155218 : }
# 191 : :
# 192 : : // Linear search (within restart block) for first key >= target
# 193 : 3488874 : SeekToRestartPoint(left);
# 194 : 7648029 : while (true) {
# 195 [ + + ]: 7648029 : if (!ParseNextKey()) {
# 196 : 775 : return;
# 197 : 775 : }
# 198 [ + + ]: 7647254 : if (Compare(key_, target) >= 0) {
# 199 : 3488099 : return;
# 200 : 3488099 : }
# 201 : 7647254 : }
# 202 : 3488874 : }
# 203 : :
# 204 : 4119 : void SeekToFirst() override {
# 205 : 4119 : SeekToRestartPoint(0);
# 206 : 4119 : ParseNextKey();
# 207 : 4119 : }
# 208 : :
# 209 : 0 : void SeekToLast() override {
# 210 : 0 : SeekToRestartPoint(num_restarts_ - 1);
# 211 [ # # ][ # # ]: 0 : while (ParseNextKey() && NextEntryOffset() < restarts_) {
# 212 : : // Keep skipping
# 213 : 0 : }
# 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 : 7785069 : bool ParseNextKey() {
# 226 : 7785069 : current_ = NextEntryOffset();
# 227 : 7785069 : const char* p = data_ + current_;
# 228 : 7785069 : const char* limit = data_ + restarts_; // Restarts come right after data
# 229 [ + + ]: 7785069 : if (p >= limit) {
# 230 : : // No more entries to return. Mark as invalid.
# 231 : 5013 : current_ = restarts_;
# 232 : 5013 : restart_index_ = num_restarts_;
# 233 : 5013 : return false;
# 234 : 5013 : }
# 235 : :
# 236 : : // Decode next entry
# 237 : 7780056 : uint32_t shared, non_shared, value_length;
# 238 : 7780056 : p = DecodeEntry(p, limit, &shared, &non_shared, &value_length);
# 239 [ + + ][ + + ]: 7780068 : if (p == nullptr || key_.size() < shared) {
# 240 : 0 : CorruptionError();
# 241 : 0 : return false;
# 242 : 7780056 : } else {
# 243 : 7780056 : key_.resize(shared);
# 244 : 7780056 : key_.append(p, non_shared);
# 245 : 7780056 : value_ = Slice(p + non_shared, value_length);
# 246 [ + + ]: 7787463 : while (restart_index_ + 1 < num_restarts_ &&
# 247 [ + + ]: 7787463 : GetRestartPoint(restart_index_ + 1) < current_) {
# 248 : 7407 : ++restart_index_;
# 249 : 7407 : }
# 250 : 7780056 : return true;
# 251 : 7780056 : }
# 252 : 7780056 : }
# 253 : : };
# 254 : :
# 255 : 3494085 : Iterator* Block::NewIterator(const Comparator* comparator) {
# 256 [ - + ]: 3494085 : if (size_ < sizeof(uint32_t)) {
# 257 : 0 : return NewErrorIterator(Status::Corruption("bad block contents"));
# 258 : 0 : }
# 259 : 3494085 : const uint32_t num_restarts = NumRestarts();
# 260 [ - + ]: 3494085 : if (num_restarts == 0) {
# 261 : 0 : return NewEmptyIterator();
# 262 : 3494085 : } else {
# 263 : 3494085 : return new Iter(comparator, data_, restart_offset_, num_restarts);
# 264 : 3494085 : }
# 265 : 3494085 : }
# 266 : :
# 267 : : } // namespace leveldb
|
