diff options
Diffstat (limited to 'table/block.cc')
| -rw-r--r-- | table/block.cc | 80 |
1 files changed, 52 insertions, 28 deletions
diff --git a/table/block.cc b/table/block.cc index 6fdfdea..3b15257 100644 --- a/table/block.cc +++ b/table/block.cc @@ -6,8 +6,10 @@ #include "table/block.h" -#include <vector> #include <algorithm> +#include <cstdint> +#include <vector> + #include "leveldb/comparator.h" #include "table/format.h" #include "util/coding.h" @@ -27,7 +29,7 @@ Block::Block(const BlockContents& contents) if (size_ < sizeof(uint32_t)) { size_ = 0; // Error marker } else { - size_t max_restarts_allowed = (size_-sizeof(uint32_t)) / sizeof(uint32_t); + size_t max_restarts_allowed = (size_ - sizeof(uint32_t)) / sizeof(uint32_t); if (NumRestarts() > max_restarts_allowed) { // The size is too small for NumRestarts() size_ = 0; @@ -51,13 +53,12 @@ Block::~Block() { // If any errors are detected, returns nullptr. Otherwise, returns a // pointer to the key delta (just past the three decoded values). static inline const char* DecodeEntry(const char* p, const char* limit, - uint32_t* shared, - uint32_t* non_shared, + uint32_t* shared, uint32_t* non_shared, uint32_t* value_length) { if (limit - p < 3) return nullptr; - *shared = reinterpret_cast<const unsigned char*>(p)[0]; - *non_shared = reinterpret_cast<const unsigned char*>(p)[1]; - *value_length = reinterpret_cast<const unsigned char*>(p)[2]; + *shared = reinterpret_cast<const uint8_t*>(p)[0]; + *non_shared = reinterpret_cast<const uint8_t*>(p)[1]; + *value_length = reinterpret_cast<const uint8_t*>(p)[2]; if ((*shared | *non_shared | *value_length) < 128) { // Fast path: all three values are encoded in one byte each p += 3; @@ -76,9 +77,9 @@ static inline const char* DecodeEntry(const char* p, const char* limit, class Block::Iter : public Iterator { private: const Comparator* const comparator_; - const char* const data_; // underlying block contents - uint32_t const restarts_; // Offset of restart array (list of fixed32) - uint32_t const num_restarts_; // Number of uint32_t entries in restart array + const char* const data_; // underlying block contents + uint32_t const restarts_; // Offset of restart array (list of fixed32) + uint32_t const num_restarts_; // Number of uint32_t entries in restart array // current_ is offset in data_ of current entry. >= restarts_ if !Valid uint32_t current_; @@ -112,9 +113,7 @@ class Block::Iter : public Iterator { } public: - Iter(const Comparator* comparator, - const char* data, - uint32_t restarts, + Iter(const Comparator* comparator, const char* data, uint32_t restarts, uint32_t num_restarts) : comparator_(comparator), data_(data), @@ -125,23 +124,23 @@ class Block::Iter : public Iterator { assert(num_restarts_ > 0); } - virtual bool Valid() const { return current_ < restarts_; } - virtual Status status() const { return status_; } - virtual Slice key() const { + bool Valid() const override { return current_ < restarts_; } + Status status() const override { return status_; } + Slice key() const override { assert(Valid()); return key_; } - virtual Slice value() const { + Slice value() const override { assert(Valid()); return value_; } - virtual void Next() { + void Next() override { assert(Valid()); ParseNextKey(); } - virtual void Prev() { + void Prev() override { assert(Valid()); // Scan backwards to a restart point before current_ @@ -162,18 +161,36 @@ class Block::Iter : public Iterator { } while (ParseNextKey() && NextEntryOffset() < original); } - virtual void Seek(const Slice& target) { + void Seek(const Slice& target) override { // Binary search in restart array to find the last restart point // with a key < target uint32_t left = 0; uint32_t right = num_restarts_ - 1; + int current_key_compare = 0; + + if (Valid()) { + // If we're already scanning, use the current position as a starting + // point. This is beneficial if the key we're seeking to is ahead of the + // current position. + current_key_compare = Compare(key_, target); + if (current_key_compare < 0) { + // key_ is smaller than target + left = restart_index_; + } else if (current_key_compare > 0) { + right = restart_index_; + } else { + // We're seeking to the key we're already at. + return; + } + } + while (left < right) { uint32_t mid = (left + right + 1) / 2; uint32_t region_offset = GetRestartPoint(mid); uint32_t shared, non_shared, value_length; - const char* key_ptr = DecodeEntry(data_ + region_offset, - data_ + restarts_, - &shared, &non_shared, &value_length); + const char* key_ptr = + DecodeEntry(data_ + region_offset, data_ + restarts_, &shared, + &non_shared, &value_length); if (key_ptr == nullptr || (shared != 0)) { CorruptionError(); return; @@ -190,8 +207,15 @@ class Block::Iter : public Iterator { } } + // We might be able to use our current position within the restart block. + // This is true if we determined the key we desire is in the current block + // and is after than the current key. + assert(current_key_compare == 0 || Valid()); + bool skip_seek = left == restart_index_ && current_key_compare < 0; + if (!skip_seek) { + SeekToRestartPoint(left); + } // Linear search (within restart block) for first key >= target - SeekToRestartPoint(left); while (true) { if (!ParseNextKey()) { return; @@ -202,12 +226,12 @@ class Block::Iter : public Iterator { } } - virtual void SeekToFirst() { + void SeekToFirst() override { SeekToRestartPoint(0); ParseNextKey(); } - virtual void SeekToLast() { + void SeekToLast() override { SeekToRestartPoint(num_restarts_ - 1); while (ParseNextKey() && NextEntryOffset() < restarts_) { // Keep skipping @@ -253,7 +277,7 @@ class Block::Iter : public Iterator { } }; -Iterator* Block::NewIterator(const Comparator* cmp) { +Iterator* Block::NewIterator(const Comparator* comparator) { if (size_ < sizeof(uint32_t)) { return NewErrorIterator(Status::Corruption("bad block contents")); } @@ -261,7 +285,7 @@ Iterator* Block::NewIterator(const Comparator* cmp) { if (num_restarts == 0) { return NewEmptyIterator(); } else { - return new Iter(cmp, data_, restart_offset_, num_restarts); + return new Iter(comparator, data_, restart_offset_, num_restarts); } } |