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 : 2583594 : inline uint32_t Block::NumRestarts() const {
# 21 : 2583594 : assert(size_ >= sizeof(uint32_t));
# 22 : 2583594 : return DecodeFixed32(data_ + size_ - sizeof(uint32_t));
# 23 : 2583594 : }
# 24 : :
# 25 : : Block::Block(const BlockContents& contents)
# 26 : : : data_(contents.data.data()),
# 27 : : size_(contents.data.size()),
# 28 : 18239 : owned_(contents.heap_allocated) {
# 29 [ - + ]: 18239 : if (size_ < sizeof(uint32_t)) {
# 30 : 0 : size_ = 0; // Error marker
# 31 : 18239 : } else {
# 32 : 18239 : size_t max_restarts_allowed = (size_ - sizeof(uint32_t)) / sizeof(uint32_t);
# 33 [ - + ]: 18239 : if (NumRestarts() > max_restarts_allowed) {
# 34 : : // The size is too small for NumRestarts()
# 35 : 0 : size_ = 0;
# 36 : 18239 : } else {
# 37 : 18239 : restart_offset_ = size_ - (1 + NumRestarts()) * sizeof(uint32_t);
# 38 : 18239 : }
# 39 : 18239 : }
# 40 : 18239 : }
# 41 : :
# 42 : 18239 : Block::~Block() {
# 43 [ + + ]: 18239 : if (owned_) {
# 44 : 484 : delete[] data_;
# 45 : 484 : }
# 46 : 18239 : }
# 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 : 24434063 : uint32_t* value_length) {
# 58 [ - + ]: 24434063 : if (limit - p < 3) return nullptr;
# 59 : 24434063 : *shared = reinterpret_cast<const uint8_t*>(p)[0];
# 60 : 24434063 : *non_shared = reinterpret_cast<const uint8_t*>(p)[1];
# 61 : 24434063 : *value_length = reinterpret_cast<const uint8_t*>(p)[2];
# 62 [ + + ]: 24434063 : if ((*shared | *non_shared | *value_length) < 128) {
# 63 : : // Fast path: all three values are encoded in one byte each
# 64 : 24433716 : p += 3;
# 65 : 24433716 : } else {
# 66 [ - + ]: 347 : if ((p = GetVarint32Ptr(p, limit, shared)) == nullptr) return nullptr;
# 67 [ - + ]: 347 : if ((p = GetVarint32Ptr(p, limit, non_shared)) == nullptr) return nullptr;
# 68 [ - + ]: 347 : if ((p = GetVarint32Ptr(p, limit, value_length)) == nullptr) return nullptr;
# 69 : 24434063 : }
# 70 : :
# 71 [ - + ]: 24434063 : if (static_cast<uint32_t>(limit - p) < (*non_shared + *value_length)) {
# 72 : 0 : return nullptr;
# 73 : 0 : }
# 74 : 24434063 : return p;
# 75 : 24434063 : }
# 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 : 24339677 : inline int Compare(const Slice& a, const Slice& b) const {
# 92 : 24339677 : return comparator_->Compare(a, b);
# 93 : 24339677 : }
# 94 : :
# 95 : : // Return the offset in data_ just past the end of the current entry.
# 96 : 5780226 : inline uint32_t NextEntryOffset() const {
# 97 : 5780226 : return (value_.data() + value_.size()) - data_;
# 98 : 5780226 : }
# 99 : :
# 100 : 26892537 : uint32_t GetRestartPoint(uint32_t index) {
# 101 : 26892537 : assert(index < num_restarts_);
# 102 : 26892537 : return DecodeFixed32(data_ + restarts_ + index * sizeof(uint32_t));
# 103 : 26892537 : }
# 104 : :
# 105 : 2546258 : void SeekToRestartPoint(uint32_t index) {
# 106 : 2546258 : key_.clear();
# 107 : 2546258 : restart_index_ = index;
# 108 : : // current_ will be fixed by ParseNextKey();
# 109 : :
# 110 : : // ParseNextKey() starts at the end of value_, so set value_ accordingly
# 111 : 2546258 : uint32_t offset = GetRestartPoint(index);
# 112 : 2546258 : value_ = Slice(data_ + offset, 0);
# 113 : 2546258 : }
# 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 : 2547117 : restart_index_(num_restarts_) {
# 124 : 2547117 : assert(num_restarts_ > 0);
# 125 : 2547117 : }
# 126 : :
# 127 : 5726154 : bool Valid() const override { return current_ < restarts_; }
# 128 : 2543380 : Status status() const override { return status_; }
# 129 : 188165 : Slice key() const override {
# 130 : 188165 : assert(Valid());
# 131 : 188165 : return key_;
# 132 : 188165 : }
# 133 : 2796266 : Slice value() const override {
# 134 : 2796266 : assert(Valid());
# 135 : 2796266 : return value_;
# 136 : 2796266 : }
# 137 : :
# 138 : 94730 : void Next() override {
# 139 : 94730 : assert(Valid());
# 140 : 94730 : ParseNextKey();
# 141 : 94730 : }
# 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 : 2543397 : void Seek(const Slice& target) override {
# 165 : : // Binary search in restart array to find the last restart point
# 166 : : // with a key < target
# 167 : 2543397 : uint32_t left = 0;
# 168 : 2543397 : uint32_t right = num_restarts_ - 1;
# 169 [ + + ]: 21201003 : while (left < right) {
# 170 : 18657606 : uint32_t mid = (left + right + 1) / 2;
# 171 : 18657606 : uint32_t region_offset = GetRestartPoint(mid);
# 172 : 18657606 : uint32_t shared, non_shared, value_length;
# 173 : 18657606 : const char* key_ptr =
# 174 : 18657606 : DecodeEntry(data_ + region_offset, data_ + restarts_, &shared,
# 175 : 18657606 : &non_shared, &value_length);
# 176 [ - + ][ - + ]: 18657606 : if (key_ptr == nullptr || (shared != 0)) {
# 177 : 0 : CorruptionError();
# 178 : 0 : return;
# 179 : 0 : }
# 180 : 18657606 : Slice mid_key(key_ptr, non_shared);
# 181 [ + + ]: 18657606 : if (Compare(mid_key, target) < 0) {
# 182 : : // Key at "mid" is smaller than "target". Therefore all
# 183 : : // blocks before "mid" are uninteresting.
# 184 : 8479343 : left = mid;
# 185 : 10178263 : } else {
# 186 : : // Key at "mid" is >= "target". Therefore all blocks at or
# 187 : : // after "mid" are uninteresting.
# 188 : 10178263 : right = mid - 1;
# 189 : 10178263 : }
# 190 : 18657606 : }
# 191 : :
# 192 : : // Linear search (within restart block) for first key >= target
# 193 : 2543397 : SeekToRestartPoint(left);
# 194 : 5682698 : while (true) {
# 195 [ + + ]: 5682698 : if (!ParseNextKey()) {
# 196 : 627 : return;
# 197 : 627 : }
# 198 [ + + ]: 5682071 : if (Compare(key_, target) >= 0) {
# 199 : 2542770 : return;
# 200 : 2542770 : }
# 201 : 5682071 : }
# 202 : 2543397 : }
# 203 : :
# 204 : 2861 : void SeekToFirst() override {
# 205 : 2861 : SeekToRestartPoint(0);
# 206 : 2861 : ParseNextKey();
# 207 : 2861 : }
# 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 : 5780226 : bool ParseNextKey() {
# 226 : 5780226 : current_ = NextEntryOffset();
# 227 : 5780226 : const char* p = data_ + current_;
# 228 : 5780226 : const char* limit = data_ + restarts_; // Restarts come right after data
# 229 [ + + ]: 5780226 : if (p >= limit) {
# 230 : : // No more entries to return. Mark as invalid.
# 231 : 3649 : current_ = restarts_;
# 232 : 3649 : restart_index_ = num_restarts_;
# 233 : 3649 : return false;
# 234 : 3649 : }
# 235 : :
# 236 : : // Decode next entry
# 237 : 5776577 : uint32_t shared, non_shared, value_length;
# 238 : 5776577 : p = DecodeEntry(p, limit, &shared, &non_shared, &value_length);
# 239 [ + + ][ + + ]: 5776581 : if (p == nullptr || key_.size() < shared) {
# 240 : 0 : CorruptionError();
# 241 : 0 : return false;
# 242 : 5776577 : } else {
# 243 : 5776577 : key_.resize(shared);
# 244 : 5776577 : key_.append(p, non_shared);
# 245 : 5776577 : value_ = Slice(p + non_shared, value_length);
# 246 [ + + ]: 5781739 : while (restart_index_ + 1 < num_restarts_ &&
# 247 [ + + ]: 5781739 : GetRestartPoint(restart_index_ + 1) < current_) {
# 248 : 5162 : ++restart_index_;
# 249 : 5162 : }
# 250 : 5776577 : return true;
# 251 : 5776577 : }
# 252 : 5776577 : }
# 253 : : };
# 254 : :
# 255 : 2547116 : Iterator* Block::NewIterator(const Comparator* comparator) {
# 256 [ - + ]: 2547116 : if (size_ < sizeof(uint32_t)) {
# 257 : 0 : return NewErrorIterator(Status::Corruption("bad block contents"));
# 258 : 0 : }
# 259 : 2547116 : const uint32_t num_restarts = NumRestarts();
# 260 [ - + ]: 2547116 : if (num_restarts == 0) {
# 261 : 0 : return NewEmptyIterator();
# 262 : 2547116 : } else {
# 263 : 2547116 : return new Iter(comparator, data_, restart_offset_, num_restarts);
# 264 : 2547116 : }
# 265 : 2547116 : }
# 266 : :
# 267 : : } // namespace leveldb
|