leveldb::Block::Iter Class Reference

Inheritance diagram for leveldb::Block::Iter:

Collaboration diagram for leveldb::Block::Iter:

Public Member Functions
	Iter (const Comparator *comparator, const char *data, uint32_t restarts, uint32_t num_restarts)
virtual bool	Valid () const
virtual Status	status () const
virtual Slice	key () const
virtual Slice	value () const
virtual void	Next ()
virtual void	Prev ()
virtual void	Seek (const Slice &target)
virtual void	SeekToFirst ()
virtual void	SeekToLast ()
Public Member Functions inherited from leveldb::Iterator
	Iterator ()
virtual	~Iterator ()
void	RegisterCleanup (CleanupFunction function, void *arg1, void *arg2)

Private Member Functions
int	Compare (const Slice &a, const Slice &b) const
uint32_t	NextEntryOffset () const
uint32_t	GetRestartPoint (uint32_t index)
void	SeekToRestartPoint (uint32_t index)
void	CorruptionError ()
bool	ParseNextKey ()

Private Attributes
const Comparator *const	comparator_
const char *const	data_
uint32_t const	restarts_
uint32_t const	num_restarts_
uint32_t	current_
uint32_t	restart_index_
std::string	key_
Slice	value_
Status	status_

Additional Inherited Members
Public Types inherited from leveldb::Iterator
typedef void(*	CleanupFunction) (void *arg1, void *arg2)

Detailed Description

Definition at line 76 of file block.cc.

Constructor & Destructor Documentation

Iter()

leveldb::Block::Iter::Iter ( const Comparator *  comparator, const char *  data, uint32_t  restarts, uint32_t  num_restarts  )

inline

Definition at line 115 of file block.cc.

      : comparator_(comparator),
        data_(data),
        restarts_(restarts),
        num_restarts_(num_restarts),
        current_(restarts_),
        restart_index_(num_restarts_) {
    assert(num_restarts_ > 0);
  }

Member Function Documentation

Compare()

int leveldb::Block::Iter::Compare ( const Slice &  a, const Slice &  b  ) const

inlineprivate

Definition at line 90 of file block.cc.

                                                           {
    return comparator_->Compare(a, b);
  }

Here is the call graph for this function:

CorruptionError()

void leveldb::Block::Iter::CorruptionError ( )

inlineprivate

Definition at line 218 of file block.cc.

                         {
    current_ = restarts_;
    restart_index_ = num_restarts_;
    status_ = Status::Corruption("bad entry in block");
    key_.clear();
    value_.clear();
  }

Here is the call graph for this function:

GetRestartPoint()

uint32_t leveldb::Block::Iter::GetRestartPoint ( uint32_t  index )

inlineprivate

Definition at line 99 of file block.cc.

                                           {
    assert(index < num_restarts_);
    return DecodeFixed32(data_ + restarts_ + index * sizeof(uint32_t));
  }

Here is the call graph for this function:

key()

virtual Slice leveldb::Block::Iter::key ( ) const

inlinevirtual

Implements leveldb::Iterator.

Definition at line 130 of file block.cc.

                            {
    assert(Valid());
    return key_;
  }

Next()

virtual void leveldb::Block::Iter::Next ( )

inlinevirtual

Implements leveldb::Iterator.

Definition at line 139 of file block.cc.

                      {
    assert(Valid());
    ParseNextKey();
  }

NextEntryOffset()

uint32_t leveldb::Block::Iter::NextEntryOffset ( ) const

inlineprivate

Definition at line 95 of file block.cc.

                                          {
    return (value_.data() + value_.size()) - data_;
  }

Here is the call graph for this function:

ParseNextKey()

bool leveldb::Block::Iter::ParseNextKey ( )

inlineprivate

Definition at line 226 of file block.cc.

                      {
    current_ = NextEntryOffset();
    const char* p = data_ + current_;
    const char* limit = data_ + restarts_;  // Restarts come right after data
    if (p >= limit) {
      // No more entries to return.  Mark as invalid.
      current_ = restarts_;
      restart_index_ = num_restarts_;
      return false;
    }

    // Decode next entry
    uint32_t shared, non_shared, value_length;
    p = DecodeEntry(p, limit, &shared, &non_shared, &value_length);
    if (p == NULL || key_.size() < shared) {
      CorruptionError();
      return false;
    } else {
      key_.resize(shared);
      key_.append(p, non_shared);
      value_ = Slice(p + non_shared, value_length);
      while (restart_index_ + 1 < num_restarts_ &&
             GetRestartPoint(restart_index_ + 1) < current_) {
        ++restart_index_;
      }
      return true;
    }
  }

Here is the call graph for this function:

Prev()

virtual void leveldb::Block::Iter::Prev ( )

inlinevirtual

Implements leveldb::Iterator.

Definition at line 144 of file block.cc.

                      {
    assert(Valid());

    // Scan backwards to a restart point before current_
    const uint32_t original = current_;
    while (GetRestartPoint(restart_index_) >= original) {
      if (restart_index_ == 0) {
        // No more entries
        current_ = restarts_;
        restart_index_ = num_restarts_;
        return;
      }
      restart_index_--;
    }

    SeekToRestartPoint(restart_index_);
    do {
      // Loop until end of current entry hits the start of original entry
    } while (ParseNextKey() && NextEntryOffset() < original);
  }

Seek()

virtual void leveldb::Block::Iter::Seek ( const Slice &  target )

inlinevirtual

Implements leveldb::Iterator.

Definition at line 165 of file block.cc.

                                         {
    // 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;
    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);
      if (key_ptr == NULL || (shared != 0)) {
        CorruptionError();
        return;
      }
      Slice mid_key(key_ptr, non_shared);
      if (Compare(mid_key, target) < 0) {
        // Key at "mid" is smaller than "target".  Therefore all
        // blocks before "mid" are uninteresting.
        left = mid;
      } else {
        // Key at "mid" is >= "target".  Therefore all blocks at or
        // after "mid" are uninteresting.
        right = mid - 1;
      }
    }

    // Linear search (within restart block) for first key >= target
    SeekToRestartPoint(left);
    while (true) {
      if (!ParseNextKey()) {
        return;
      }
      if (Compare(key_, target) >= 0) {
        return;
      }
    }
  }

Here is the call graph for this function:

SeekToFirst()

virtual void leveldb::Block::Iter::SeekToFirst ( )

inlinevirtual

Implements leveldb::Iterator.

Definition at line 205 of file block.cc.

                             {
    SeekToRestartPoint(0);
    ParseNextKey();
  }

SeekToLast()

virtual void leveldb::Block::Iter::SeekToLast ( )

inlinevirtual

Implements leveldb::Iterator.

Definition at line 210 of file block.cc.

                            {
    SeekToRestartPoint(num_restarts_ - 1);
    while (ParseNextKey() && NextEntryOffset() < restarts_) {
      // Keep skipping
    }
  }

SeekToRestartPoint()

void leveldb::Block::Iter::SeekToRestartPoint ( uint32_t  index )

inlineprivate

Definition at line 104 of file block.cc.

                                          {
    key_.clear();
    restart_index_ = index;
    // current_ will be fixed by ParseNextKey();

    // ParseNextKey() starts at the end of value_, so set value_ accordingly
    uint32_t offset = GetRestartPoint(index);
    value_ = Slice(data_ + offset, 0);
  }

status()

virtual Status leveldb::Block::Iter::status ( ) const

inlinevirtual

Implements leveldb::Iterator.

Definition at line 129 of file block.cc.

{ return status_; }

Valid()

virtual bool leveldb::Block::Iter::Valid ( ) const

inlinevirtual

Implements leveldb::Iterator.

Definition at line 128 of file block.cc.

{ return current_ < restarts_; }

value()

virtual Slice leveldb::Block::Iter::value ( ) const

inlinevirtual

Implements leveldb::Iterator.

Definition at line 134 of file block.cc.

                              {
    assert(Valid());
    return value_;
  }

Member Data Documentation

comparator_

const Comparator* const leveldb::Block::Iter::comparator_

private

Definition at line 78 of file block.cc.

current_

uint32_t leveldb::Block::Iter::current_

private

Definition at line 84 of file block.cc.

data_

const char* const leveldb::Block::Iter::data_

private

Definition at line 79 of file block.cc.

key_

std::string leveldb::Block::Iter::key_

private

Definition at line 86 of file block.cc.

num_restarts_

uint32_t const leveldb::Block::Iter::num_restarts_

private

Definition at line 81 of file block.cc.

restart_index_

uint32_t leveldb::Block::Iter::restart_index_

private

Definition at line 85 of file block.cc.

restarts_

uint32_t const leveldb::Block::Iter::restarts_

private

Definition at line 80 of file block.cc.

status_

Status leveldb::Block::Iter::status_

private

Definition at line 88 of file block.cc.

value_

Slice leveldb::Block::Iter::value_

private

Definition at line 87 of file block.cc.

---

The documentation for this class was generated from the following file:

• table/block.cc