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 <vector> 10 #include <algorithm> 11 #include "leveldb/comparator.h" 12 #include "table/format.h" 13 #include "util/coding.h" 14 #include "util/logging.h" 15 16 namespace leveldb { 17 18 inline uint32_t Block::NumRestarts() const { 19 assert(size_ >= sizeof(uint32_t)); 20 return DecodeFixed32(data_ + size_ - sizeof(uint32_t)); 21 } 22 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 29 } else { 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() 33 size_ = 0; 34 } else { 35 restart_offset_ = size_ - (1 + NumRestarts()) * sizeof(uint32_t); 36 } 37 } 38 } 39 40 Block::~Block() { 41 if (owned_) { 42 delete[] data_; 43 } 44 } 45 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 derefence past "limit". 50 // 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, 54 uint32_t* shared, 55 uint32_t* non_shared, 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 63 p += 3; 64 } else { 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; 68 } 69 70 if (static_cast<uint32_t>(limit - p) < (*non_shared + *value_length)) { 71 return NULL; 72 } 73 return p; 74 } 75 76 class Block::Iter : public Iterator { 77 private: 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 82 83 // current_ is offset in data_ of current entry. >= restarts_ if !Valid 84 uint32_t current_; 85 uint32_t restart_index_; // Index of restart block in which current_ falls 86 std::string key_; 87 Slice value_; 88 Status status_; 89 90 inline int Compare(const Slice& a, const Slice& b) const { 91 return comparator_->Compare(a, b); 92 } 93 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_; 97 } 98 99 uint32_t GetRestartPoint(uint32_t index) { 100 assert(index < num_restarts_); 101 return DecodeFixed32(data_ + restarts_ + index * sizeof(uint32_t)); 102 } 103 104 void SeekToRestartPoint(uint32_t index) { 105 key_.clear(); 106 restart_index_ = index; 107 // current_ will be fixed by ParseNextKey(); 108 109 // ParseNextKey() starts at the end of value_, so set value_ accordingly 110 uint32_t offset = GetRestartPoint(index); 111 value_ = Slice(data_ + offset, 0); 112 } 113 114 public: 115 Iter(const Comparator* comparator, 116 const char* data, 117 uint32_t restarts, 118 uint32_t num_restarts) 119 : comparator_(comparator), 120 data_(data), 121 restarts_(restarts), 122 num_restarts_(num_restarts), 123 current_(restarts_), 124 restart_index_(num_restarts_) { 125 assert(num_restarts_ > 0); 126 } 127 128 virtual bool Valid() const { return current_ < restarts_; } 129 virtual Status status() const { return status_; } 130 virtual Slice key() const { 131 assert(Valid()); 132 return key_; 133 } 134 virtual Slice value() const { 135 assert(Valid()); 136 return value_; 137 } 138 139 virtual void Next() { 140 assert(Valid()); 141 ParseNextKey(); 142 } 143 144 virtual void Prev() { 145 assert(Valid()); 146 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) { 151 // No more entries 152 current_ = restarts_; 153 restart_index_ = num_restarts_; 154 return; 155 } 156 restart_index_--; 157 } 158 159 SeekToRestartPoint(restart_index_); 160 do { 161 // Loop until end of current entry hits the start of original entry 162 } while (ParseNextKey() && NextEntryOffset() < original); 163 } 164 165 virtual void Seek(const Slice& target) { 166 // Binary search in restart array to find the last restart point 167 // with a key < target 168 uint32_t left = 0; 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, 175 data_ + restarts_, 176 &shared, &non_shared, &value_length); 177 if (key_ptr == NULL || (shared != 0)) { 178 CorruptionError(); 179 return; 180 } 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. 185 left = mid; 186 } else { 187 // Key at "mid" is >= "target". Therefore all blocks at or 188 // after "mid" are uninteresting. 189 right = mid - 1; 190 } 191 } 192 193 // Linear search (within restart block) for first key >= target 194 SeekToRestartPoint(left); 195 while (true) { 196 if (!ParseNextKey()) { 197 return; 198 } 199 if (Compare(key_, target) >= 0) { 200 return; 201 } 202 } 203 } 204 205 virtual void SeekToFirst() { 206 SeekToRestartPoint(0); 207 ParseNextKey(); 208 } 209 210 virtual void SeekToLast() { 211 SeekToRestartPoint(num_restarts_ - 1); 212 while (ParseNextKey() && NextEntryOffset() < restarts_) { 213 // Keep skipping 214 } 215 } 216 217 private: 218 void CorruptionError() { 219 current_ = restarts_; 220 restart_index_ = num_restarts_; 221 status_ = Status::Corruption("bad entry in block"); 222 key_.clear(); 223 value_.clear(); 224 } 225 226 bool ParseNextKey() { 227 current_ = NextEntryOffset(); 228 const char* p = data_ + current_; 229 const char* limit = data_ + restarts_; // Restarts come right after data 230 if (p >= limit) { 231 // No more entries to return. Mark as invalid. 232 current_ = restarts_; 233 restart_index_ = num_restarts_; 234 return false; 235 } 236 237 // Decode next entry 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) { 241 CorruptionError(); 242 return false; 243 } else { 244 key_.resize(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_) { 249 ++restart_index_; 250 } 251 return true; 252 } 253 } 254 }; 255 256 Iterator* Block::NewIterator(const Comparator* cmp) { 257 if (size_ < sizeof(uint32_t)) { 258 return NewErrorIterator(Status::Corruption("bad block contents")); 259 } 260 const uint32_t num_restarts = NumRestarts(); 261 if (num_restarts == 0) { 262 return NewEmptyIterator(); 263 } else { 264 return new Iter(cmp, data_, restart_offset_, num_restarts); 265 } 266 } 267 268 } // namespace leveldb 269