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.
5 // Decodes the blocks generated by block_builder.cc.
7 #include "table/block.h"
11 #include "leveldb/comparator.h"
12 #include "table/format.h"
13 #include "util/coding.h"
14 #include "util/logging.h"
18 inline uint32_t Block::NumRestarts() const {
19 assert(size_ >= sizeof(uint32_t));
20 return DecodeFixed32(data_ + size_ - sizeof(uint32_t));
23 Block::Block(const BlockContents& contents)
24 : data_(contents.data.data()),
25 size_(contents.data.size()),
26 owned_(contents.heap_allocated) {
27 if (size_ < sizeof(uint32_t)) {
28 size_ = 0; // Error marker
30 size_t max_restarts_allowed = (size_-sizeof(uint32_t)) / sizeof(uint32_t);
31 if (NumRestarts() > max_restarts_allowed) {
32 // The size is too small for NumRestarts()
35 restart_offset_ = size_ - (1 + NumRestarts()) * sizeof(uint32_t);
46 // Helper routine: decode the next block entry starting at "p",
47 // storing the number of shared key bytes, non_shared key bytes,
48 // and the length of the value in "*shared", "*non_shared", and
49 // "*value_length", respectively. Will not dereference past "limit".
51 // If any errors are detected, returns NULL. Otherwise, returns a
52 // pointer to the key delta (just past the three decoded values).
53 static inline const char* DecodeEntry(const char* p, const char* limit,
56 uint32_t* value_length) {
57 if (limit - p < 3) return NULL;
58 *shared = reinterpret_cast<const unsigned char*>(p)[0];
59 *non_shared = reinterpret_cast<const unsigned char*>(p)[1];
60 *value_length = reinterpret_cast<const unsigned char*>(p)[2];
61 if ((*shared | *non_shared | *value_length) < 128) {
62 // Fast path: all three values are encoded in one byte each
65 if ((p = GetVarint32Ptr(p, limit, shared)) == NULL) return NULL;
66 if ((p = GetVarint32Ptr(p, limit, non_shared)) == NULL) return NULL;
67 if ((p = GetVarint32Ptr(p, limit, value_length)) == NULL) return NULL;
70 if (static_cast<uint32_t>(limit - p) < (*non_shared + *value_length)) {
76 class Block::Iter : public Iterator {
78 const Comparator* const comparator_;
79 const char* const data_; // underlying block contents
80 uint32_t const restarts_; // Offset of restart array (list of fixed32)
81 uint32_t const num_restarts_; // Number of uint32_t entries in restart array
83 // current_ is offset in data_ of current entry. >= restarts_ if !Valid
85 uint32_t restart_index_; // Index of restart block in which current_ falls
90 inline int Compare(const Slice& a, const Slice& b) const {
91 return comparator_->Compare(a, b);
94 // Return the offset in data_ just past the end of the current entry.
95 inline uint32_t NextEntryOffset() const {
96 return (value_.data() + value_.size()) - data_;
99 uint32_t GetRestartPoint(uint32_t index) {
100 assert(index < num_restarts_);
101 return DecodeFixed32(data_ + restarts_ + index * sizeof(uint32_t));
104 void SeekToRestartPoint(uint32_t index) {
106 restart_index_ = index;
107 // current_ will be fixed by ParseNextKey();
109 // ParseNextKey() starts at the end of value_, so set value_ accordingly
110 uint32_t offset = GetRestartPoint(index);
111 value_ = Slice(data_ + offset, 0);
115 Iter(const Comparator* comparator,
118 uint32_t num_restarts)
119 : comparator_(comparator),
122 num_restarts_(num_restarts),
124 restart_index_(num_restarts_) {
125 assert(num_restarts_ > 0);
128 virtual bool Valid() const { return current_ < restarts_; }
129 virtual Status status() const { return status_; }
130 virtual Slice key() const {
134 virtual Slice value() const {
139 virtual void Next() {
144 virtual void Prev() {
147 // Scan backwards to a restart point before current_
148 const uint32_t original = current_;
149 while (GetRestartPoint(restart_index_) >= original) {
150 if (restart_index_ == 0) {
152 current_ = restarts_;
153 restart_index_ = num_restarts_;
159 SeekToRestartPoint(restart_index_);
161 // Loop until end of current entry hits the start of original entry
162 } while (ParseNextKey() && NextEntryOffset() < original);
165 virtual void Seek(const Slice& target) {
166 // Binary search in restart array to find the last restart point
167 // with a key < target
169 uint32_t right = num_restarts_ - 1;
170 while (left < right) {
171 uint32_t mid = (left + right + 1) / 2;
172 uint32_t region_offset = GetRestartPoint(mid);
173 uint32_t shared, non_shared, value_length;
174 const char* key_ptr = DecodeEntry(data_ + region_offset,
176 &shared, &non_shared, &value_length);
177 if (key_ptr == NULL || (shared != 0)) {
181 Slice mid_key(key_ptr, non_shared);
182 if (Compare(mid_key, target) < 0) {
183 // Key at "mid" is smaller than "target". Therefore all
184 // blocks before "mid" are uninteresting.
187 // Key at "mid" is >= "target". Therefore all blocks at or
188 // after "mid" are uninteresting.
193 // Linear search (within restart block) for first key >= target
194 SeekToRestartPoint(left);
196 if (!ParseNextKey()) {
199 if (Compare(key_, target) >= 0) {
205 virtual void SeekToFirst() {
206 SeekToRestartPoint(0);
210 virtual void SeekToLast() {
211 SeekToRestartPoint(num_restarts_ - 1);
212 while (ParseNextKey() && NextEntryOffset() < restarts_) {
218 void CorruptionError() {
219 current_ = restarts_;
220 restart_index_ = num_restarts_;
221 status_ = Status::Corruption("bad entry in block");
226 bool ParseNextKey() {
227 current_ = NextEntryOffset();
228 const char* p = data_ + current_;
229 const char* limit = data_ + restarts_; // Restarts come right after data
231 // No more entries to return. Mark as invalid.
232 current_ = restarts_;
233 restart_index_ = num_restarts_;
238 uint32_t shared, non_shared, value_length;
239 p = DecodeEntry(p, limit, &shared, &non_shared, &value_length);
240 if (p == NULL || key_.size() < shared) {
245 key_.append(p, non_shared);
246 value_ = Slice(p + non_shared, value_length);
247 while (restart_index_ + 1 < num_restarts_ &&
248 GetRestartPoint(restart_index_ + 1) < current_) {
256 Iterator* Block::NewIterator(const Comparator* cmp) {
257 if (size_ < sizeof(uint32_t)) {
258 return NewErrorIterator(Status::Corruption("bad block contents"));
260 const uint32_t num_restarts = NumRestarts();
261 if (num_restarts == 0) {
262 return NewEmptyIterator();
264 return new Iter(cmp, data_, restart_offset_, num_restarts);
268 } // namespace leveldb